Name
Abstract | ||
|---|---|---|
A simple topological graph G is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. G is called saturated if no further edge can be added without violating this condition. We construct saturated simple topological graphs with n vertices and O ( n ) edges. For every k 1 , we give similar constructions for k-simple topological graphs, that is, for graphs drawn in the plane so that any two edges have at most k points in common. We show that in any k-simple topological graph, any two independent vertices can be connected by a curve that crosses each of the original edges at most 2k times. Another construction shows that the bound 2k cannot be improved. Several other related problems are also considered. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.comgeo.2014.10.008 | Comput. Geom. |
Keywords | Field | DocType |
Simple topological graph,Saturated topological graph,Pseudoline arrangement | Discrete mathematics,Topology,Combinatorics,Cycle graph,1-planar graph,Topological graph theory,Multiple edges,Mathematics,Planar graph,Voltage graph,Topological graph,Edge-graceful labeling | Journal |
Volume | Issue | ISSN |
48 | 4 | Computational Geometry: Theory and Applications 48 (2015), Issue
4, 295-310 |
Citations | PageRank | References |
1 | 0.48 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan Kyncl | 1 | 18 | 5.20 |
| János Pach | 2 | 2366 | 292.28 |
| Rados Radoicic | 3 | 146 | 18.45 |
| Géza Tóth | 4 | 581 | 55.60 |