Every Graph Admits an Unambiguous Bold Drawing

Pach, János (2012) Every Graph Admits an Unambiguous Bold Drawing. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 332-342 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_32).

Full text not available from this repository.

Abstract

Let r and w be a fixed positive numbers, w < r. In a bold drawing of a graph, every vertex is represented by a disk of radius r, and every edge by a narrow rectangle of width w. We solve a problem of van Kreveld [K09] by showing that every graph admits a bold drawing in which the region occupied by the union of the disks and rectangles representing the vertices and edges does not contain any disk of radius r other than the ones representing the vertices.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_32
Classifications:P Styles > P.999 Others
ID Code:1267

Repository Staff Only: item control page

References

Barequet, G., Goodrich, M.T., Riley, C.: Drawing planar graphs with large vertices and thick edges. J. Graph Algorithms Appl. 8, 3–20 (2004)

Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. ACM 39, 1–54 (1992)

Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discrete & Computational Geometry 4, 387–421 (1989)

Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with fat edges. Int. J. Found. Comput. Sci. 17, 1143–1164 (2006)

Erdös, P., Szekeres, G.: A combinatorial problem Geometry. Compositio Mathematica 2, 463–470 (1935)

Graham, R., Rothschild, B., Spencer, J.H.: Ramsey Theory. John Wiley and Sons, New York (1990)

van Kreveld, M.: Bold graph drawings. In: Proc. Canadian Conference on Computational Geometry, CCCG 2009 (2009), http://cccg.ca/proceedings/2009/cccg09_31.pdf; Also Computational Geometry: Theory & Applications (to appear)

Mulmuley, K.: A fast planar partition algorithm, I. In: Proc. 29th FOCS,pp. 580–589 (1988)

North, S.C.: Drawing Graphs with Neato (2004), http://www.graphviz.org/Documentation/neatoguide.pdf

Ramsey, F.P.: On a problem of formal logic. Proc. London Math. Soc. Series 30(2), 264–286 (1930)