String graphs, graph drawing, computing with curves on surface

UR-CS Participating Faculty: Daniel Stefankovic

Project Description

This project studies theoretical problems arising in the area of graph drawing (network diagram visualization). Examples of questions studied are:

Bibliography

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.

  1. 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.

  2. Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.
    Spiraling and folding: the word view.
    Algorithmica, 2009, (DOI 10.1007/s00453-009-9362-8).

  3. Michael Pelsmajer, Marcus Schaefer, Daniel Stefankovic.
    Removing even crossings on surfaces.
    European Journal of Combinatorics, 30:1704-1717, 2009.

  4. 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.

  5. 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.

  6. Michael Pelsmajer, Marcus Schaefer, Daniel Stefankovic.
    Removing even crossings.
    Journal of Combinatorial Theory B (JCTB) 97(4):489–500, 2007.

  7. 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.

  8. Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic.
    Spiralling and folding: the topological view.
    19th Canadian Conference on Computational Geometry (CCCG 2007), pp. 73–76, 2007.

  9. 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.

  10. 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.

  11. Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.
    Algorithms for normal curves and surfaces.
    COCOON 2002, p. 370-380, 2002.