Name
Abstract | ||
|---|---|---|
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers )i n the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-LAYER PLANARIZATION problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP -complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-LAYER PLANARIZATION problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-LAYER PLANARIZATION problem in O(k · 6k +| G|) time and the 1-LAYER PLANARIZATION problem in O(3k ·| G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s00453-005-1181-y | Algorithmica |
Keywords | DocType | Volume |
Graph drawing,Planarization,Crossing minimization,Sugiyama approach,Fixed-parameter tractability,NP-complete,Graph algorithms | Journal | 45 |
Issue | ISSN | Citations |
2 | 0178-4617 | 7 |
PageRank | References | Authors |
0.54 | 10 | 12 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vida Dujmovic | 1 | 416 | 43.34 |
| Michael R. Fellows | 2 | 4138 | 319.37 |
| Michael T. Hallett | 3 | 479 | 42.87 |
| Matthew Kitching | 4 | 87 | 6.43 |
| Giuseppe Liotta | 5 | 1356 | 112.95 |
| Catherine McCartin | 6 | 296 | 20.26 |
| Naomi Nishimura | 7 | 292 | 19.82 |
| Prabhakar Ragde | 8 | 529 | 91.67 |
| Frances A. Rosamond | 9 | 304 | 15.94 |
| Matthew Suderman | 10 | 142 | 10.03 |
| Sue Whitesides | 11 | 1449 | 197.63 |
| David R. Wood | 12 | 1073 | 96.22 |