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 nvertex graph G can be drawn in the plane such that each pair of crossing edges is independent and there is a crossingfree edge that connects their endpoints, then G has O(n) edges. Graphs that admit such drawings are related to quasiplanar graphs and to maximal 1planar and fanplanar graphs.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.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 