Peripheral cycle

In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs. A peripheral cycle in a graph can be defined formally in one of several equivalent ways: is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges and in , there exists a path in that starts with , ends with , and has no interior vertices belonging to . is peripheral if it is an induced cycle with the property that the subgraph formed by deleting the edges and vertices of is connected. If is any subgraph of , a bridge of is a minimal subgraph of that is edge-disjoint from and that has the property that all of its points of attachments (vertices adjacent to edges in both and ) belong to . A simple cycle is peripheral if it has exactly one bridge. The equivalence of these definitions is not hard to see: a connected subgraph of (together with the edges linking it to ), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in . Peripheral cycles appear in the theory of polyhedral graphs, that is, 3-vertex-connected planar graphs. For every planar graph , and every planar embedding of , the faces of the embedding that are induced cycles must be peripheral cycles. In a polyhedral graph, all faces are peripheral cycles, and every peripheral cycle is a face. It follows from this fact that (up to combinatorial equivalence, the choice of the outer face, and the orientation of the plane) every polyhedral graph has a unique planar embedding.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (8)

Related people (2)

Related concepts (13)

Related lectures (1)

Steinitz's theorem

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

Clique-sum

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have at most k vertices.

Polyhedral graph

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs. The Schlegel diagram of a convex polyhedron represents its vertices and edges as points and line segments in the Euclidean plane, forming a subdivision of an outer convex polygon into smaller convex polygons (a convex drawing of the graph of the polyhedron).

Covers matrices, linear applications, vector spaces, and bijective functions.

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general ...

2017

Electromagnetic Modelling of Planar Circuits Embedded in Laterally Shielded Multilayered Media

Laleh Golestanirad

Multilayered media with printed circuits embedded between their dielectric layers are one of the most successful technologies for manufacturing planar structures with a very promising performance-to-price ratio. These planar structures include many differe ...

EPFL2011

Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility

Jean-Pierre Hubaux, Jun Luo

The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged ...

2010