Ackerman, Eyal and Keszegh, Balázs and Vizer, Máté (2016) On the size of planarly connected crossing graphs. Lecture Notes in Computer Science (LNCS) : Proceedings of Graph Drawing 2016. (In Press)
|
Text
1509.02475v3.pdf Download (358kB) | Preview |
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.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | Balázs Keszegh |
| Date Deposited: | 03 Oct 2016 14:08 |
| Last Modified: | 03 Oct 2016 14:15 |
| URI: | http://real.mtak.hu/id/eprint/40904 |
Actions (login required)
 |
Edit Item |
