Name
Abstract | ||
|---|---|---|
A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. It is known that the problem of testing 1-planarity of a graph is NP-complete. In this paper, we study outer-1-planar graphs. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a given graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00453-014-9890-8 | Algorithmica |
Keywords | Field | DocType |
Graph drawing,1-Planar graphs,Outer 1-planar graphs,1-Planarity,1-Planar embedding | Discrete mathematics,Combinatorics,Crossing number (graph theory),Planarity testing,Graph embedding,Planar straight-line graph,Algorithm,Book embedding,Apex graph,Butterfly graph,Planar graph,Mathematics | Conference |
Volume | Issue | ISSN |
72 | 4 | 0178-4617 |
Citations | PageRank | References |
12 | 0.56 | 24 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Seok-Hee Hong | 1 | 1057 | 91.85 |
| Peter Eades | 2 | 962 | 69.36 |
| naoki katoh | 3 | 1101 | 187.43 |
| Giuseppe Liotta | 4 | 341 | 30.83 |
| Pascal Schweitzer | 5 | 41 | 2.24 |
| Yusuke Suzuki | 6 | 50 | 2.00 |