Name
Abstract | ||
|---|---|---|
A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n-O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n-O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jcta.2006.08.002 | Journal of Combinatorial Theory Series A |
Keywords | Field | DocType |
simple proof,non-simple quasi-planar graph,topological graph,quasi-planar graph,simple quasi-planar topological graph,b. aronov,lower bound,maximum number,linear number,j. pach,geometric graph,planar graph,upper bound,upper and lower bounds | Pseudoforest,Discrete mathematics,Combinatorics,Multigraph,Cycle graph,Matching (graph theory),Mixed graph,Multiple edges,Mathematics,Topological graph,Dense graph | Journal |
Volume | Issue | ISSN |
114 | 3 | 0097-3165 |
Citations | PageRank | References |
22 | 1.48 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eyal Ackerman | 1 | 188 | 19.80 |
| Gábor Tardos | 2 | 1261 | 140.58 |