On fan-crossing graphs

DOI10.1016/J.TCS.2020.07.002zbMATH Open1461.68145arXiv1712.06840OpenAlexW3043294381MaRDI QIDQ2202017FDOQ2202017

Authors: Franz J. Brandenburg 

Publication date: 17 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A fan is a set of edges with a single common endpoint. A graph is fan-crossing if it admits a drawing in the plane so that each edge is crossed by edges of a fan. It is fan-planar if, in addition, the common endpoint is on the same side of the crossed edge. A graph is adjacency-crossing if it admits a drawing so that crossing edges are adjacent. Then it excludes independent crossings which are crossings by edges with no common endpoint. Adjacency-crossing allows triangle-crossings in which an edge crosses the edges of a triangle, which is excluded at fan-crossing graphs. We show that every adjacency-crossing graph is fan-crossing. Thus triangle-crossings can be avoided. On the other hand, there are fan-crossing graphs that are not fan-planar, whereas for every fan-crossing graph there is a fan-planar graph on the same set of vertices and with the same number of edges. Hence, fan-crossing and fan-planar graphs are different, but they do not differ in their density with at most 5n - 10 edges for graphs of size n.

Full work available at URL: https://arxiv.org/abs/1712.06840

Recommendations

• On fan-crossing and fan-crossing free graphs
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• On the Number of Edges of Fan-Crossing Free Graphs
• On the Number of Edges of Fan-Crossing Free Graphs
• On fans in multigraphs
• Fan-planar graphs
• On the spanning fan-connectivity of graphs
• Crossing graphs of fiber-complemented graphs
• Crossing graphs of fiber-complemented graphs
• Fan-planar graphs: combinatorial properties and complexity results

zbMATH Keywords

graph drawingfansindependent edgesedge crossings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Ein Sechsfarbenproblem auf der Kugel
• On the Density of Maximal 1-Planar Graphs
• Quasi-planar graphs have a linear number of edges
• On the maximum number of edges in quasi-planar graphs
• Title not available (Why is that?)
• Recognizing optimal 1-planar graphs in linear time
• On grids in topological graphs
• An annotated bibliography on 1-planarity
• Topological graphs with no large grids
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• On fan-crossing and fan-crossing free graphs
• Fan-planarity: properties and complexity
• On the Number of Edges of Fan-Crossing Free Graphs
• A First Order Logic Definition of Beyond-Planar Graphs

Cited In (13)

• The density of fan-planar graphs
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• Simplifying non-simple fan-planar drawings
• Compatibility fans for graphical nested complexes
• Title not available (Why is that?)
• Straight-line drawings of 1-planar graphs
• Simplifying Non-Simple Fan-Planar Drawings
• Title not available (Why is that?)
• Characterizing 5-map graphs by 2-fan-crossing graphs
• Crossing graphs of fiber-complemented graphs
• On the Number of Edges of Fan-Crossing Free Graphs
• The family of fan-planar graphs
• Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity

This page was built for publication: On fan-crossing graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2202017)