Name
Abstract | ||
|---|---|---|
We prove that if an n-vertex graph G can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then G has O(n) edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal 1-planar and fan-planar graphs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-50106-2_24 | GRAPH DRAWING AND NETWORK VISUALIZATION (GD 2016) |
Keywords | Field | DocType |
Planar graphs, Crossing edges, Crossing-free edge, Fanplanar graphs, 1-planar graphs | Discrete mathematics,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Pathwidth,1-planar graph,Planar graph,Mathematics,Maximal independent set,Dense graph | Journal |
Volume | Issue | ISSN |
9801 | 1 | 0302-9743 |
Citations | PageRank | References |
2 | 0.36 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eyal Ackerman | 1 | 188 | 19.80 |
| Balázs Keszegh | 2 | 156 | 24.36 |
| Máté Vizer | 3 | 27 | 14.06 |