On triangulating planar graphs under the four-connectivity constraint

DOI10.1007/3-540-58218-5_8zbMath1502.68210OpenAlexW1589741320MaRDI QIDQ5056168

Goos Kant, Michael Kaufmann, Therese C. Biedl

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_8

Mathematics Subject Classification ID

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 (2)

Triangulating planar graphs while minimizing the maximum degree ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear algorithm for embedding planar graphs using PQ-trees
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Some simplified NP-complete graph problems
• Arboricity and Subgraph Listing Algorithms
• Rectangular duals of planar graphs
• A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph
• Augmentation Problems
• Smallest Augmentations to Biconnect a Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete

This page was built for publication: On triangulating planar graphs under the four-connectivity constraint