Loading...
Please wait, while we are loading the content...
Similar Documents
On the crossing number of almost planar graphs (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Mohar, Bojan |
| Abstract | If G is a plane graph and x, y ∈ V (G), then the dual distance of x and y is equal to the minimum number of crossings of G with a closed curve in the plane joining x and y. Riskin [7] proved that if G0 is a 3connected cubic planar graph, and x, y are its vertices at dual distance d, then the crossing number of the graph G0 + xy is equal to d. Riskin asked if his result holds for arbitrary 3-connected planar graphs. In this paper it is proved that this is not the case (not even for every 5-connected planar graph G0). Povzetek: Analizirana je Riskinova teza o planarnih grafih. 1 |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dual Distance Almost Planar Graph Crossing Number 3connected Cubic Planar Graph Closed Curve Graph G0 Xy 5-connected Planar Graph G0 Arbitrary 3-connected Planar Graph Plane Graph Minimum Number |
| Content Type | Text |
| Resource Type | Article |
