Connectivity of plane triangulations

DOI10.1016/0020-0190(90)90142-KzbMath0696.68087MaRDI QIDQ911313

Jean-Paul Laumond

Publication date: 1990

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

zbMATH Keywords

graph theoryconnectivitycomputational geometryplane triangulationsarticulation sets

Mathematics Subject Classification ID

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

Related Items (5)

Finding Hamiltonian cycles in Delaunay triangulations is NP-complete ⋮ Packing disks by flipping and flowing ⋮ Domination of maximal \(K_4\)-minor free graphs and maximal \(K_{2, 3}\)-minor free graphs, and disproofs of two conjectures on planar graphs ⋮ Triangulating with high connectivity. ⋮ Four-connected triangulations of planar point sets

Cites Work

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

This page was built for publication: Connectivity of plane triangulations