This project studies theoretical problems arising in the area of graph drawing (network diagram visualization).
Examples of questions studied are:
The crossing number of a graph is the minimum number of crossings in a plane drawing of the graph. One of the reasons
that the crossing number is rather tricky to deal with, is the topological nature of the definition. Tutte (1970) initiated the
study of an algebraic variant of the concept of crossing number. Since then other alternatives to the crossing number were introduced.
What are the relations between these variants? Can they be used to compute the crossing number of a graph more efficiently?
The planarity problem asks if a given graph can be drawn in the plane with no intersections between its edges.
Suppose that we relax the constraints to allow for some pairs of the edges to intersect - can the graph be drawn in the plane now? How hard is it to find such a drawing?
This is a list of selected journal (except when the work has not yet
appeared in journal/book form) papers, from or related to this project, by
University of Rochester authors.
Michael Pelsmajer, Marcus Schaefer, and Daniel Stefankovic.
Odd crossing number is not crossing number. Graph Drawing, 2005, LNCS 3843, p. 386-396, Springer Verlag, 2005.
Marcus Schaefer and Daniel Stefankovic.
Decidability of string graphs. J. Comput. System Sci., 68:2, p. 319-334, 2004.
A preliminary version appeared in STOC 2001, p. 241-246.
Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.
String graphs in NP. J. Comput. System Sci. 67:2, p. 365-380, 2003.
A preliminary version appered in STOC 2002, p. 1-6.
Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.
Algorithms for normal curves and surfaces. COCOON 2002, p. 370-380, 2002.
Peter Hui, Marcus Schaefer, and Daniel Stefankovic.
Graph Drawing, 2004, LNCS 3383, Springer-Verlag, 2004, p. 318-328.