Marcus Schaefer

Research Interests and Curriculum Vitae

Research interests: computability, complexity, combinatorics (graph theory).

 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 Postscript and pdf.

 

 

Book

Papers and Technical Reports

Graph Theory

• Removing Independently Even Crossings, Pelsmajer, Schaefer, Štefankovič, Graph Drawing 2009.
• Crossing Number of Graphs with Rotation Systems. Pelsmajer, Schaefer, Štefankovič, Algorithmica, 2009.
• The Complexity of Nonrepetitive Coloring. Marx, Schaefer; Discrete Applied Mathematics, 157, 13--18, 2009.
• Complexity of Some Geometric 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 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. Schaefer, Štefankovič, Sedgwick, Canadian Conference on Computational Geometry (CCCG 07), 2007.
• Spiraling and Folding: The Word View. Schaefer, Štefankovič, Sedgwick, to appear in Algorithmica, 2009.
• 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