Connectivity of plane triangulations

DOI10.1016/0020-0190(90)90142-KMaRDI QIDQ911313zbMATH OpenFDO

Authors J.-P. Laumond

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

graph theorycomputational geometryconnectivityplane triangulationsarticulation sets

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Connectivity of planar graphs
• Hamiltonian-connectedness of triangulations with few separating triangles
• Publication:4340555
• Publication:4006000
• On triangulating planar graphs under the four-connectivity constraint

Cites work

• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• An upper bound on the shortness exponent of inscribable polytopes
• Arboricity and Subgraph Listing Algorithms
• Bridges and Hamiltonian circuits in planar graphs
• Dividing a Graph into Triconnected Components
• Drawing plane graphs nicely
• Efficient Planarity Testing
• Enumeration of articulation pairs of a planar graph
• Hamiltonian cycles in planar triangulations with no separating triangles
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs

Cited in

(13)

• Domination of maximal \(K_4\)-minor free graphs and maximal \(K_{2, 3}\)-minor free graphs, and disproofs of two conjectures on planar graphs
• Test for intersection between a plane and a connected compact polyhedron
• Connected perimeter of planar sets
• Packing disks by flipping and flowing
• Triangles n-Connectivity in Simplicial 2-Complexes
• Robotics and artificial intelligence
• Enumeration of articulation pairs of a planar graph
• Four-connected triangulations of planar point sets
• scientific article; zbMATH DE number 57414 (Why is no real title available?)
• Triangulating with high connectivity.
• Tutte embeddings of tetrahedral meshes
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• Connectivity of planar graphs

This page was built for publication: Connectivity of plane triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911313)