On the size of planarly connected crossing graphs
Preprint
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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- New bounds on the maximum number of edges in k-quasi-planar graphsComputational Geometry, 2015
- On grids in topological graphsComputational Geometry, 2014
- Coloring-free intersection graphs of geometric objects in the planeEuropean Journal of Combinatorics, 2012
- On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing EdgesDiscrete & Computational Geometry, 2009
- On the maximum number of edges in quasi-planar graphsJournal of Combinatorial Theory, Series A, 2007
- Relaxing Planarity for Topological Graphs2006
- Research Problems in Discrete Geometry2005
- Graphs drawn with few crossings per edgeCombinatorica, 1997
- Quasi-planar graphs have a linear number of edgesCombinatorica, 1997
- A turán-type theorem on chords of a convex polygonJournal of Combinatorial Theory, Series B, 1992