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, Daniel Stefankovic.
Removing independently even crossings. SIAM Journal on Discrete Mathematics 24(2):379–393, 2010.
A preliminary version appeared in Graph Drawing (GD) 2009, p. 201-206.
Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.
Spiraling and folding: the word view. Algorithmica, 2009, (DOI 10.1007/s00453-009-9362-8).
Michael Pelsmajer, Marcus Schaefer, Daniel Stefankovic.
Removing even crossings on surfaces. European Journal of Combinatorics, 30:1704-1717, 2009.
Michael Pelsmajer, Marcus Schaefer, Daniel Stefankovic.
Odd crossing number is not crossing number. Discrete and Computational Geometry (DCG) 39(1-3):442–454, 2008.
A preliminary version appeared in Graph Drawing (GD) 2005, p. 386-396.
Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic.
Computing Dehn twists and geometric intersection numbers in polynomial time. 20th Canadian Conference in Computational Geometry (CCCG 2008), pp. 111–114,
2008.
Michael Pelsmajer, Marcus Schaefer, Daniel Stefankovic.
Removing even crossings. Journal of Combinatorial Theory B (JCTB) 97(4):489–500, 2007.
Peter Hui, Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic.
Train tracks and confluent drawings. Algorithmica 47(4):465-479, 2007.
A preliminary version appeared in Graph Drawing (GD) 2004, p. 318-328.
Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic.
Spiralling and folding: the topological view. 19th Canadian Conference on Computational Geometry (CCCG 2007), pp. 73–76, 2007.
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.
