Name
Abstract | ||
|---|---|---|
In this paper, we show that for outerplanar graphsGthe problem of augmentingGby adding a minimum number of edges such that the augmented graphG′ is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space. It is also shown that augmenting a biconnected outerplanar graph to a maximal outerplanar graph while minimizing the maximum degree can be achieved in polynomial time. These augmentation problems arise in the area of drawing outerplanar graphs. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1006/jagm.1996.0034 | J. Algorithms |
Keywords | Field | DocType |
outerplanar graph,polynomial time,maximum degree,linear time | Graph theory,Discrete mathematics,Graph,Combinatorics,Outerplanar graph,Partial k-tree,Planar,Degree (graph theory),Time complexity,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 1 | 0196-6774 |
Citations | PageRank | References |
19 | 1.07 | 3 |
Authors | ||
1 | ||