Abstract | ||
---|---|---|
A k-outerplanar graph is a graph that can be drawn in the plane without crossing such that after k-fold removal of the vertices on the outer-face there are no vertices left. In this paper, we study how to triangulate a k-outerplanar graph while keeping its outerplanarity small. Specifically, we show that not all k-outerplanar graphs can be triangulated so that the result is k-outerplanar, but they can be triangulated so that the result is (k+1)-outerplanar. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.dam.2014.10.017 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Outer-planarity,Triangulating,Triangulated disk,Treewidth,Branchwidth | Journal | 181 |
Issue | ISSN | Citations |
C | 0166-218X | 3 |
PageRank | References | Authors |
0.41 | 9 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Therese Biedl | 1 | 902 | 106.36 |