Name
Abstract | ||
|---|---|---|
. Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords
are graph augmentation from the field of graph algorithms and mesh generation from the field of computational geometry. We
consider the triangulation problem for planar graphs under the constraint to satisfy 4-connectivity. A 4-connected planar
graph has no separating triangles, i.e., cycles of length 3 which are not a face.
We show that triangulating embedded planar graphs without introducing new separating triangles can be solved in linear time
and space. If the initial graph had no separating triangle, the resulting triangulation is 4-connected. If the planar graph
is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with
at most twice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar
graph can be made 4-connected while maintaining planarity. Several related remarks and results are included. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/PL00009182 | Algorithmica |
Keywords | Field | DocType |
graph algorithms,triangulating planar graphs,four-connectivity constraint,triangulation,planarity.,Key words. Graph algorithms, Triangulation, Planarity. | Discrete mathematics,Outerplanar graph,Combinatorics,Line graph,Forbidden graph characterization,Computer science,Planar straight-line graph,Book embedding,Pathwidth,1-planar graph,Planar graph | Conference |
Volume | Issue | ISSN |
19 | 4 | 1432-0541 |
Citations | PageRank | References |
22 | 1.21 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Therese Biedl | 1 | 902 | 106.36 |
| Goos Kant | 2 | 565 | 51.19 |
| Michael Kaufmann | 3 | 361 | 25.45 |