Marcus Schaefer

Research Interests and Curriculum Vitae

Research interests: graph drawing, graph theory, computational complexity, computability.

 I obtained my Ph.D. degree in Computer Science from

the University of Chicago in June 1999 with Stuart Kurtz.

My Curriculum Vitae is available in pdf.

 

 

Books

Papers and Technical Reports

Graph Theory and Graph Drawing

• RAC-Drawability is ∃ℝ-complete and Related Results, Schaefer, Journal of Graph Algorithms and Applications, 27(9), 2023. Conference version in Graph Drawing 2021.
• The Complexity of Angular Resolution, Schaefer, Journal of Graph Algorithms and Applications, 27(7), 2023.
• Hanani-Tutte for Radial Planarity II, Fulek, Pelsmajer, Schaefer, Electronic Journal of Combinatorics, P1.14, 2023 (earlier version in Graph Drawing, 2016).
• Hanani-Tutte and Hierarchical Partial Planarity, SIAM Journal on Discrete Mathematics, 36(4), 2022.
• The degenerate crossing number and higher-genus embeddings, Schaefer, Štefankovič, Journal of Graph Algorithms and Applications, 26(1), 2022.
• A New Algorithm for Embedding Planar Graphs at Fixed Vertex Locations, Schaefer, Electronic Journal of Combinatorics, 2021.
• Taking a Detour; or, Gioan’s Theorem, and Pseudolinear Drawings of Complete Graphs, Schaefer, Discrete & Computational Geometry, 66, 2021.
• Strong Hanani-Tutte on the Torus, Fulek, Pelsmajer, Schaefer, accepted to SoCG'21, 2021 (conference version).
• On the Complexity of Some Geometric Problems With Fixed Parameters, Schaefer, Journal of Graph Algorithms and Applications, 25(1), 2021.
• Complexity of Geometric k-Planarity for fixed k, Schaefer, Journal of Graph Algorithms and Applications, 25(1), 2021.
• A Proof of Levi's Extension Lemma, Schaefer, Arxiv, 2019.
• Link Crossing Number is NP-hard, de Mesmay, Schaefer, Sedgewick, Journal of Knot Theory and Its Ramifications, 29(6), 2020.
• A Note on the Crossing Number of Spiders, Fallon, Hogenson, Keough, Lomelí,Schaefer, Soberón, to appear in JCMCC, 2018.
• Hanani-Tutte for Radial Planarity, Fulek, Pelsmajer, Schaefer, Journal of Graph Algorithms and Applications , 21(1), 2017 (earlier in Graph Drawing 2015).
• The Degenerate Crossing Number and Higher-Genus Embeddings, Schaefer,  Štefankovič, Graph Drawing, 2015.
• Multi-Sided Boundary Labeling, Kindermann, Niedermann, Rutter, Schaefer, Schulz, Wolff , Algorithmica, 2015.
• Drawing Partially Embedded and Simultaneously Planar Graphs, Chan, Frati, Gutwenger, Lubiw, Mutzel, Schaefer, Special Issue on Graph Drawing, 2015.
• A crossing lemma for the pair-crossing number, Ackerman, Schaefer, Graph Drawing, 2014.
• Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph, Schaefer, Graph Drawing, 2014.
• Practical Experience with Hanani-Tutte for Testing c-Planarity, Gutwenger, Mutzel, Schaefer, ALENEX, 2014.
• Block Additivity of Z₂ -embeddings, Schaefer,  Štefankovič, Graph Drawing, 2013.
• (last update: May 2024): The Graph Crossing Number and its Variants: A Survey, Schaefer, Electronic Journal of Combinatorics, Dynamic Survey 21, 2013; updated May 2024.
• Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants, Schaefer, Graph Drawing, 2012.
  • Video of presentation
• Hanani-Tutte, Monotone Drawings, and Level-Planarity, Fulek, Pelsmajer, Schaefer, Štefankovič,  in Thirty Essays on Geometric Graph Theory, Springer 2012.
• Adjacent Crossings Do Matter, Fulek, Pelsmajer, Schaefer, Štefankovič,Graph Drawing, 2011.
• Hanani-Tutte and Related Results, Schaefer, in Geometry-Intuitive, Discrete, and Convex, Springer, 2013.
• Some Unexpected(ly) Open Problems, Schaefer, Midsummer Combinatorial Workshop, Prague, 2009.
• Removing Independently Even Crossings, Pelsmajer, Schaefer, Štefankovič, SIAM Journal on Discrete Mathematics, 24(2), 379-393, 2010.
• Crossing Number of Graphs with Rotation Systems. Pelsmajer, Schaefer, Štefankovič, Algorithmica, 60(3), 679-702, 2011.
• The Complexity of Nonrepetitive Coloring. Marx, Schaefer; Discrete Applied Mathematics, 157, 13--18, 2009.
• Complexity of Some Geometric and Topological Problems. Schaefer, Graph Drawing 2009.
• Strong Hanani-Tutte on the Projective Plane. Pelsmajer, Schaefer, Stasi; SIAM Journal on Discrete Mathematics, 23(3), 1317-1323, 2009.
• On the Induced Matching Problem. Kanj, Pelsmajer, Schaefer, Xia; STACS, 2008.
• Odd Crossing Number and Crossing Number Are Not the Same. Pelsmajer, Schaefer, Štefankovič, Discrete and Computational Geometry, 39 (1-3), 442-454, 2008.
• Simultaneous Geometric Graph Embeddings. Estrella-Balderrama, Gassner, Juenger, Percan, Schaefer, Schulz; Graph Drawing, 2007.
• Δ_k-Confluent and O_k-confluent Graphs. Pelsmajer, Schaefer, Stern; DePaul University Technical Report, TR 07-004, 2007.
• Removing Even Crossings on Surfaces. Pelsmajer, Schaefer, Štefankovič; Eurocomb, 2007. (Earlier version: Removing Even Crossings, Continued, DePaul University Technical Report, TR 06-016, 2006.)
• Crossing Numbers and Parameterized Complexity. Pelsmajer, Schaefer, Štefankovič, Graph Drawing, 2007.
• Simultaneous Graph Embeddings with Fixed Edges. Gassner, Jünger, Percan, Schaefer, Schulz, WG, 2006.
• Removing Even Crossings. Pelsmajer, Schaefer, Štefankovič, Journal of Combinatorial Theory, Series B, 97, 2007.
• Train Tracks and Confluent Drawings. Hui, Pelsmajer, Schaefer, Štefankovič, Algorithmica, 47(4), 465-479, 2007.
• Decidability of String Graphs. Schaefer, Štefankovič, Journal of Computer and System Sciences, 68, 319–334, 2004.
• Induced Graph Ramsey Theory. Schaefer, Shah; Ars Combinatoria, 66, 3--21, 2003.
• Solvability of Graph Inequalities.Schaefer, Štefankovič, SIAM Journal on Discrete Mathematics, 19, 728-743, 2005.

Complexity Theory

• The Existential Theory of the Reals as a Complexity Class: A Compendium, Schaefer, Cardinal, Miltzow, 2024. Arxiv version: arxiv2407.18006. Bibliography file: https://tinyurl.com/ER-bibliography.
• Beyond the Existential Theory of the Reals, Schaefer, Štefankovič. Theory of Computing Systems, 2023. Arxiv version: arXiv2210.00571, 2022.
• The Complexity of Tensory Rank. Schaefer, Štefankovič, Theory of Computing Systems, 2017. Arxiv version: arXiv1612.04338 (fixes error in the universality result).
• Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. Schaefer, Štefankovič, Theory of Computing Systems, 2015.
• Realizability of Graphs and Linkages, Schaefer, in Thirty Essays on Geometric Graph Theory, Springer 2013.
• The Graph Sandwich Problem for a coNP property. Schaefer, DePaul University Technical Report, TR 06-011, 2006.
• Parameterized Algorithms for Feedback Vertex Set. Kanj, Pelsmajer, Schaefer, IWPEC 2004.
• Completeness in the Polynomial-Time Hierarchy: Part II. Schaefer, Umans; Sigact News, December 2002.
• (last update 8/23/08): Completeness in the Polynomial-Time Hierarchy: A Compendium. Schaefer, Umans; Sigact News, September 2002. 
• Strong Reductions and Immunity for Exponential Time. Schaefer, Stephan; STACS 2003.
• Recognizing String Graphs in NP. Schaefer, Štefankovič, Sedgwick, Journal of Computer and System Sciences, 67, 365-380, 2003.
• Deciding the VC-dimension is sigma_3 complete, II. Schaefer; DePaul University Technical Report TR00-006, 2000.
• Deciding the K-dimension is PSPACE-complete. Schaefer; Conference on Computational Complexity, 2000.
• Graph Ramsey Theory and the Polynomial Hierarchy. Schaefer, Journal of Computer and System Sciences, 62, 2, 290–322, 2001.
• Simplicity and Strong Reductions. Schaefer, Fenner; University of Chicago Technical Report TR-97-06, 1997.
• Hyper-polynomial hierarchies and the NP-jump. Fenner, Homer, Pruim, Schaefer, Theoretical Computer Science, 262, pp. 241­256, 2001
• Deciding the VC-dimension is sigma_3 complete. Schaefer; Journal of Computer and System Sciences, 58, 177–182, 1999.

Computational Geometry

• Spiraling and Folding: The Topological View (arxiv). Schaefer, Štefankovič, Sedgwick,  Discrete & Computational Geometry, 2023.
• Spiraling and Folding: The Word View. Schaefer, Štefankovič, Sedgwick, Algorithmica, 60(3), 609-626, 2011.
• Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time, Schaefer, Štefankovič, Sedgwick, CCCG, 2008.
• Paired Pointset Traversal. Hui, Schaefer, ISAAC, 2004.
• Algorithms for Normal Curves and Surfaces. Schaefer, Štefankovič, Sedgwick, COCOON 2002, 370-380, 2002.

Computability Theory

• Cuppability of Simple and Hypersimple sets. Kummer, Schaefer; Notre-Dame Journal of Formal Logic, 48,  349-369, 2007.
• Bounded Immunity and Btt-Reductions. Schaefer, Fenner; Mathematical Logic Quarterly, 45, 1, 3–21, 1999.
• A Guided Tour of Minimal Indices and Shortest Descriptions. Schaefer; Archives for Mathematical Logic, 37, 521–548, 1998.
• Computability Of Convex Sets . Kummer, Schaefer; STACS 1995.

Marcus Schaefer