On triangulating planar graphs under the four-connectivity constraint
From MaRDI portal
Publication:1386769
DOI10.1007/PL00009182zbMath0898.68053OpenAlexW1997180465MaRDI QIDQ1386769
Goos Kant, Therese C. Biedl, Michael Kaufmann
Publication date: 11 October 1998
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009182
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
The longest common subsequence problem for sequences with nested arc annotations. ⋮ Non-aligned Drawings of Planar Graphs ⋮ Flip distance between two triangulations of a point set is NP-complete ⋮ Compact visibility representation of 4-connected plane graphs ⋮ Unnamed Item ⋮ On triangulating \(k\)-outerplanar graphs ⋮ RECONSTRUCTING CONVEX POLYGONS AND CONVEX POLYHEDRA FROM EDGE AND FACE COUNTS IN ORTHOGONAL PROJECTIONS ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Unnamed Item ⋮ Closed rectangle-of-influence drawings for irreducible triangulations ⋮ Fixed-parameter algorithms for protein similarity search under mRNA structure constraints ⋮ Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections ⋮ Transversal structures on triangulations: A combinatorial study and straight-line drawings ⋮ Open rectangle-of-influence drawings of inner triangulated plane graphs ⋮ Triangulating Planar Graphs While Keeping the Pathwidth Small
