Michael J. Pelsmajer
Publications and Work in progress

Often it happens that what is essentially a single project will result in more than one type of publication, typically with a later version (e.g., for a math journal) having more details or building on an earlier version (e.g., an extended abstract in the proceedings of a computer science conference). Multiple versions of a single project will be grouped together, with all links to a single version of the paper. All publications listed here have been peer-reviewed/refereed; technical reports are not listed.

Adjacent Crossings Do Matter
Journal of Graph Algorithms and Applications, to appear.
Adjacent Crossings Do Matter
in Graph Drawing 2011, Lecture Notes in Comput. Sci. 7034, Springer, Berlin, 2012, 343-354.
with R. Fulek, M. Schaefer, and D. Stefankovic.

Hanani-Tutte, Monotone Drawings, and Level-Planarity
Thirty Essays on Geometric Graph Theory, J. Pach ed., to appear.
Hanani-Tutte and Monotone Drawings
in WG 2011, Lecture Notes in Comput. Sci. 6986, Springer, Berlin, 2011, 283-294.
with R. Fulek, M. Schaefer, and D. Stefankovic.

On the induced matching problem
J. Comput. Syst. Sci., 77(6), 2011, 1058-1070.
On the induced matching problem
in 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Leibniz International Proceedings in Informatics 1, 2008, 397-408.
with I. Kanj and M. Schaefer.

Crossing Number of Graphs with Rotation Systems
Algorithmica 60(3) (Special issue: Algorithms, Combinatorics, & Geometry), 2011, 679-702.
Crossing Number of Graphs with Rotation Systems
in Graph drawing 2007, Lecture Notes in Comput. Sci. 4875, Springer, Berlin, 2008, 3–12.
with M. Schaefer and D. Stefankovic.

Dominating sets in triangulations on surfaces
Ars Mathematica Contemporanea 4(1) (Special issue in memory of Michael O. Albertson), 2011, 177-204.
with H. Liu.

Generalized centrality in trees
in Advances in Interdisciplinary Applied Discrete Mathematics, H. Kaul, H.M. Mulder (Eds.), 2011, 127–147.
with K. B. Reid.

Dominating sets in plane triangulations
Discrete Math. 310(17-18), 2010, 2221-2230.
with E. L. C. King.

Removing Independently Even Crossings
SIAM J. Discrete Math. 24(2), 2010, 379-393.
Removing Independently Even Crossings
in Graph Drawing 2009, Lecture Notes in Comput. Sci. 5849, Springer, Berlin, 2010, 201-206.
with M. Schaefer and D. Stefankovic.

k-robust single-message transmission
SIAM J. Discrete Math. 24(1), 2010, 301-321.
k-robust single-message transmission
in Combinatorial and algorithmic aspects of networking (CAAN 2004), Lecture Notes in Comput. Sci. 3405, Springer, Berlin, 2005, 90-101.
with A. Kündgen and R. Ramamurthi.

Removing even crossings on surfaces
European J. Combin. 30(7)) (EuroComb’07: Combinatorics, Graph Theory and Applications), 2009, 1704–1717.
Removing even crossings on surfaces
Electronic Notes in Discrete Mathematics 29, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '07), 2007, 85–90.
with M. Schaefer and D. Stefankovic.

Equitable list coloring and tree-width
J. Graph Theory 61(2), 2009, 127–139.

Strong Hanani-Tutte on the projective plane
SIAM J. Discrete Math. 23(3), 2009, 1317-1323.
with M. Schaefer and D. Stasi.

Fast edge colorings with fixed number of colors to minimize imbalance
Journal of Graph Algorithms and Applications 12(4), 2008, 401–417.
Fast edge colorings with fixed number of colors to minimize imbalance
in Foundations of Software Technology and Theoretical Computer Science 2006 (FSTTCS 2006), Lecture Notes in Comput. Sci. 4337, Springer, Berlin, 2006, 117-128.
Minimizing Tunable Ports in Optical Networks
to appear in Combinatorial and algorithmic aspects of networking (CAAN 2005), Internet Mathematics.
with G. Calinescu.

Axiomization of the Center Function on Trees
Australas. J. Combin. 41, 2008, 223–226.
with H. M. Mulder and K. B. Reid.

Odd Crossing Number and Crossing Number Are Not the Same
Discrete & Computational Geometry 39(1-3), 2008, 442-454.
Republished:
Twentieth Anniversary Volume: Discrete & Computational Geometry, J.E. Goodman, J. Pach, R. Pollack (Eds.), 2009.
Odd crossing number is not crossing number
in Graph drawing, Lecture Notes in Comput. Sci. 3843, Springer, Berlin, 2006, 386-396.
with M. Schaefer and D. Stefankovic.

Nonrepetitive colorings of graphs of bounded tree-width
Discrete Math. (Simonovits '06) 308(19), 2008, 4473–4478.
with A. Kündgen.

Crossing Numbers and Parameterized Complexity
in Graph Drawing 2007, Lecture Notes in Comput. Sci. 4875, Springer, Berlin, 2008, 31–36.
with M. Schaefer and D. Stefankovic.

Train tracks and confluent drawings
Algorithmica 47(4), 2007, 465-479.
with P. Hui, M. Schaefer, and D. Stefankovic.

Removing even crossings
J. Combin. Theory Ser. B 97(4), 2007, 489-500.
Removing even crossings
in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, 105-110.
with M. Schaefer and D. Stefankovic.

Transversal numbers of translates of a convex body
Discrete Math. 306(18), 2006, 2166-2173.
with S.-J. Kim, K. Nakprasit, and J. Skokan.

Integer Programming Solutions for Several Optimization Problems in Graph Theory
in Computers and Their Applications (CATA 2005), 2005, 50-55.
with J. Luttamaguzi, Z. Shen, and B. Yang.

Graph minors and reliable single message transmission
SIAM J. Discrete Math. 19(4), 2005, 815-847.
with F. E. Fich, A. Kündgen, and R. Ramamurthi.

Parameterized Algorithms for Feedback Vertex Set
in IWPEC 2004, Lecture Notes in Comput. Sci. 3162, Springer, Berlin, 2004, 235-247.
with I. Kanj and M. Schaefer.

Maximum induced linear forests in outerplanar graphs
Graphs Combin. 20(1), 2004, 121-129.

The toughness of a toroidal graph with connectivity 3 and girth 6 is exactly 1
Graphs Combin. 20(2), 2004, 181-183.
with W. Cao.

Equitable list-coloring for graphs of maximum degree 3
J. Graph Theory 47(1), 2004, 1-8.

A list analogue of equitable coloring
J. Graph Theory 44(3), 2003, 166-177.
with A. V. Kostochka and D. B. West.


Finding minors in graphs with a given path structure
Submitted.
with A. Kündgen and R. Ramamurthi.

Approximating the Quadratic Knapsack Problem and its Generalization
Submitted.
with H. Kaul and S. Kapoor.

Maximum induced forests in graphs of bounded treewidth
Submitted.
with G. G. Chappell.

Δk and Ok confluent graphs
In progress.
with M. Schaefer and K. Stern.

Last updated by pelsmajer AT iit DOT edu on 7/27/2012

Back to Michael Pelsmajer's home page