Face-width of embedded graphs
From MaRDI portal
The face-width of a graph embedded in a surface is the smallest number of points that the graph has in common with a noncontractible closed curve. Robertson and Seymour introduced this concept as a measure of how dense the graph is on the surface. The reviewer found a polynomial time algorithm for determining the face-width, and Robertson and Vitray proved that embeddings of large face-width are always minimum genus embeddings, and that they share many properties with planar embeddings. The subjects which are treated in detail in the present survey include face-width \(2\) or \(3\), graphs which are minimal in the sense that every minor has smaller face-width, embedding flexibility, uniqueness of embeddings, orientable genus of nonorientable embeddings, and combinatorial properties of embeddings of large width. Some unsolved problems are included. NEWLINENEWLINENEWLINEThe last one, Conjecture 9.7 has recently been proved in a joint work by T. Böhme, the author, and the reviewer. The same subjects are treated in a forthcoming book by the author and the reviewer.
Recommendations
- Uniqueness and minimality of large face-width embeddings of graphs
- scientific article; zbMATH DE number 4156462
- Face colorings of embedded graphs
- Algorithms for the edge-width of an embedded graph
- Face distributions of embeddings of complete graphs
- scientific article; zbMATH DE number 4177081
- Thickness and outerthickness for embedded graphs
- The plane-width of graphs
- Embeddings of graphs of fixed treewidth and bounded degree
- On the plane-width of graphs
Cites work
- 2-connected spanning subgraphs of planar 3-connected graphs
- 2-Isomorphic Graphs
- 2-walks in circuit graphs
- 2‐connected coverings of bounded degree in 3‐connected graphs
- 3-trees in polyhedral maps
- 4-connected projective planar graphs are Hamiltonian
- A minimax theorem on circuits in projective graphs
- A simple construction of high representativity triangulations
- A Theorem on Planar Graphs
- Almost all rooted maps have large representativity
- An infinite set of torus triangulations of connectivity 5 whose graphs are not uniquely embeddable in the torus
- Apex graphs with embeddings of face-width three
- Circuits in graphs embedded on the torus
- Classification of minimal graphs of given face-width on the torus
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Computing the orientable genus of projective graphs
- Constructing the graphs that triangulate both the torus and the Klein bottle
- Decomposition of graphs on surfaces and a homotopic circulation theorem
- Decomposition theorems for the torus, projective plane and Klein bottle
- Degenerate and star colorings of graphs on surfaces
- Densely embedded graphs
- Disjoint circuits of prescribed homotopies in a graph on a compact surface
- Disjoint essential cycles
- Embeddings of graphs with no short noncontractible cycles
- Five-coloring maps on surfaces
- Five-connected toroidal graphs are Hamiltonian
- Generating closed 2-cell embeddings in the torus and the projective plane
- Generating locally-cyclic triangulations of surfaces
- Generating projective plane polyhedral maps
- Generating the triangulations of the projective plane
- Graph minors. VII: Disjoint paths on a surface
- Graph minors. XX: Wagner's conjecture
- Graph theory with applications
- Graphs on the torus and geometry of numbers
- Grid minors of graphs on the torus
- scientific article; zbMATH DE number 431515 (Why is no real title available?)
- scientific article; zbMATH DE number 4211829 (Why is no real title available?)
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 17630 (Why is no real title available?)
- scientific article; zbMATH DE number 1332109 (Why is no real title available?)
- scientific article; zbMATH DE number 475582 (Why is no real title available?)
- scientific article; zbMATH DE number 475597 (Why is no real title available?)
- scientific article; zbMATH DE number 475598 (Why is no real title available?)
- scientific article; zbMATH DE number 4117852 (Why is no real title available?)
- scientific article; zbMATH DE number 786140 (Why is no real title available?)
- scientific article; zbMATH DE number 969111 (Why is no real title available?)
- scientific article; zbMATH DE number 3188197 (Why is no real title available?)
- Irreducible triangulations of surfaces
- Minimal embeddings in the projective plane
- Nonhamiltonian triangulations with large connectivity and representativity
- Note on irreducible triangulations of surfaces
- On essential and inessential polygons in embedded graphs
- On Short Noncontractible Cycles in Embedded Graphs
- On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle
- On the noninterpolation of polyhedral maps
- On the orientable genus of graphs embedded in the klein bottle
- On the orientable genus of graphs with bounded nonorientable genus
- On the uniqueness of kernels
- Planar graphs on nonplanar surfaces
- Planar graphs on the projective plane
- Re-embedding of projective-planar graphs
- Representations of Planar Graphs
- Separating and nonseparating disjoint homotopic cycles in graph embeddings
- Spanning Eulerian subgraphs of bounded degree in triangulations
- Spanning planar subgraphs of graphs in the torus and Klein bottle
- Spanning trees in locally planar triangulations
- Systems of curves on surfaces
- The 2 and 3 representative projective planar embeddings
- The construction and classification of self-dual spherical polyhedra
- The graph genus problem is NP-complete
- Three-coloring graphs embedded on surfaces with all faces even-sided
- Trees in Polyhedral Graphs
- Trees in triangulations
- Triangulating a surface with a prescribed graph
- Unique and faithful embeddings of projective-planar graphs
- Unique embeddings of simple projective plane polyhedral maps
- Uniqueness and faithfulness of embedding of toroidal graphs
- Uniqueness and minimality of large face-width embeddings of graphs
Cited in
(19)- Classification of minimal graphs of given face-width on the torus
- Apex graphs with embeddings of face-width three
- Half-arc-transitive graphs and chiral hypermaps.
- On \(3\)-connected plane graphs without triangular faces
- Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds
- Uniqueness and minimality of large face-width embeddings of graphs
- Combinatorial Local Planarity and the Width of Graph Embeddings
- scientific article; zbMATH DE number 475597 (Why is no real title available?)
- scientific article; zbMATH DE number 475598 (Why is no real title available?)
- scientific article; zbMATH DE number 1359497 (Why is no real title available?)
- Graph Drawing
- Regular maps on surfaces with large planar width
- On local operations that preserve symmetries and on preserving polyhedrality of maps
- The connectivity of the dual
- Preserving and increasing symmetries of polyhedral maps
- Integer programs with bounded subdeterminants and two nonzeros per row
- The effect of symmetry-preserving operations on 3-connectivity
- Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds
- Densely embedded graphs
This page was built for publication: Face-width of embedded graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2702745)
