
arXiv: 1308.5079
A visibility representation is a classical drawing style of planar graphs. It displays the vertices of a graph as horizontal vertex-segments, and each edge is represented by a vertical edge-segment touching the segments of its end vertices; beyond that segments do not intersect. We generalize visibility to 1-visibility, where each edge- (vertex-) segment crosses at most one vertex- (edge-) segment. In other words, a vertex is crossed by at most one edge, and vice-versa. We show that 1-visibility properly extends 1-planarity and develop a linear time algorithm to compute a 1-visibility representation of an embedded 1-planar graph on O(n^2) area. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. Concerning density, both 1-visible and 1-planar graphs of size $n$ have at most 4n-8 edges. However, for every n >= 7 there are 1-visible graphs with 4n-8 edge which are not 1-planar.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), linear time algorithm, Graph representations (geometric and intersection representations, etc.), 68R10, G.2.2, Planar graphs; geometric and topological aspects of graph theory, 1-visible graph, Computer Science - Computational Geometry, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), linear time algorithm, Graph representations (geometric and intersection representations, etc.), 68R10, G.2.2, Planar graphs; geometric and topological aspects of graph theory, 1-visible graph, Computer Science - Computational Geometry, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 26 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
