Dr. Steven Chaplick

I have moved to Maastricht University!

See my new webpage: https://www.maastrichtuniversity.nl/p70068141

Teaching

WS 2019/2020: Lecturer for Advanced Algorithms
SS 2019: Lecturer for Graph Visualization
WS 2018/2019: Lecturer for Exact Algorithms
SS 2018: Lecturer for Graph Visualization
WS 2017/2018: Lecturer for Computational Geometry
SS 2017: Lecturer for Graph Visualization
WS 2016/2017: Lecturer for Approximation Algorithms
SS 2016: Lecturer for Graph Visualization
WS 2015/2016: Lecturer for Computational Geometry

Research Interests

My primary area of interest is algorithmic graph theory and my current research focuses on intersection representations of graphs, efficient methods for graph class recognition, and optimization problems on restricted graph classes.

CV

(see: here for my full CV)

Postdoctoral Work:

Since Sept. 2015:
Postdoc in the Chair of Computer Science I, Universität Würzburg.
Jan. 2014 – June 2015:
Postdoc in the Algorithmic and Discrete Mathematics Group, TU Berlin. *
Feb. 2013 – Dec. 2013:
Postdoc in the Department of Applied Mathematics, Charles University in Prague. *
Jan. 2012 – Jan. 2013:
Visiting Researcher: Wilfrid Laurier University (Waterloo, Canada), Simon Fraser University (Vancouver, Canada), University of Toronto (Toronto, Canada), Haifa University (Haifa, Israel).

* These positions were supported by the EuroCores EUROGIGA project GraDR.

Studies:

Feb. 2008 – Jan. 2012:
PhD in Computer Science at the University of Toronto (Advisor: Derek Corneil).
Sept. 2006 – Jan. 2008:
M.Sc in Computer Science at the University of Toronto (Advisor: Derek Corneil).
Sept. 2001 – June 2006:
B.Math double degree in Combinatorics & Optimization and Computer Science at the University of Waterloo.

Academic Service :

Program Committee Member
WG 2018 : 44th International Workshop on Graph-Theoretic Concepts in Computer Science.
GD 2018 : 26th International Symposium on Graph Drawing and Network Visualization.
(recent) Workshop Organization:
(2018) Workshop on Constrained Recognition Problems. Co-located with ICALP.
(2017) Workshop on Geometric Perspectives in Graph Drawing and Information Visualization. Co-located with SoCG.
(2016) 19th Korean Workshop on Computational Geometry.
(2016) Workshop on Geometric Representations of Graphs. Co-located with SoCG/STOC.
Referee Experience
Journals: CGTA (Journal of Computational Geometry – Theory and Applications), DAM (Discrete Applied Mathematics), DMTCS (Discrete Mathematics & Theoretical Computer Science), IPL (Information Pro- cessing Letters), TCS (Theoretical Computer Science).
Conferences: CALDAM (Conf. on Algorithms and Discrete Applied Mathematics), CIAC (Int. Conf. on Al- gorithms and Complexity), EUROCOMB (Eur. Conf. on Combinatorics, Graph Theory and Applications), FSTTCS (Foundations of Software Technology and Theoretical Computer Science Conf.), GD (Int. Symp. on Graph Drawing and Network Visualization), ICALP (Int. Colloquium on Automata, Languages, and Programming), IWOCA (Int. Workshop on Combinatorial Algorithms), LAGOS (Latin-American Algo- rithms, Graphs, and Optimization Symp.), SoCG (Symp. on Computational Geometry), SODA (ACM- SIAM Symp. on Discrete Algorithms), STACS (Int. Symp. on Theoretical Aspects of Computer Science), STOC (ACM Symp. on Theory of Computing), WADS (Algorithms and Data Structures Symp.), WG (Int. Workshop on Graph-Theoretic Concepts in Computer Science).

Publications

2019[ to top ]

Intersection Graphs of Non-crossing Paths Chaplick, Steven in Graph-Theoretic Concepts in Computer Science, I. Sau, D. M. Thilikos (eds.) (2019). 311–324.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree. Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). For intersection graphs of NC paths of a tree, the dominating set problem is shown to be solvable in linear time. Also, each such graph is shown to have a Hamiltonian cycle if and only if it is 2-connected, and to have a Hamiltonian path if and only if its block-cutpoint tree is a path.

@inproceedings{10.1007/978-3-030-30786-8_24, abstract = {We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree. Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). For intersection graphs of NC paths of a tree, the dominating set problem is shown to be solvable in linear time. Also, each such graph is shown to have a Hamiltonian cycle if and only if it is 2-connected, and to have a Hamiltonian path if and only if its block-cutpoint tree is a path.}, address = {Cham}, author = {Chaplick, Steven}, booktitle = {Graph-Theoretic Concepts in Computer Science}, editor = {Sau, Ignasi and Thilikos, Dimitrios M.}, keywords = {publication}, pages = {311–324}, publisher = {Springer International Publishing}, title = {Intersection Graphs of Non-crossing Paths}, year = 2019 }
Compact drawings of 1-planar graphs with right-angle crossings and few bends Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Computational Geometry: Theory and Applications (2019). 84 50–68.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O(n)×O(n). Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O(n3)×O(n3). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

@article{CHAPLICK201950, abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O(n)×O(n). Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O(n3)×O(n3). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.}, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Computational Geometry: Theory and Applications}, keywords = {publication}, note = {Special Issue on the 34th European Workshop on Computational Geometry}, pages = {50-68}, title = {Compact drawings of 1-planar graphs with right-angle crossings and few bends}, volume = 84, year = 2019 }
Kernelization of Graph Hamiltonicity: Proper H-Graphs Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dusan; Zeman, Peter in WADS, Lecture Notes in Computer Science, Z. Friggstad, J.-R. Sack, M. R. Salavatipour (eds.) (2019). 296–310.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Bir{\'o}, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi) graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results.

@inproceedings{10.1007/978-3-030-24766-9_22, abstract = {We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Bir{\'o}, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi) graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results.}, address = {Cham}, author = {Chaplick, Steven and Fomin, Fedor V. and Golovach, Petr A. and Knop, Dusan and Zeman, Peter}, booktitle = {WADS}, editor = {Friggstad, Zachary and Sack, Jörg-Rüdiger and Salavatipour, Mohammad R.}, keywords = {publication}, pages = {296–310}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Kernelization of Graph Hamiltonicity: Proper H-Graphs}, year = 2019 }
Morphing Contact Representations of Graphs. Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Lozzo, Giordano Da; Roselli, Vincenzo in 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs), G. Barequet, Y. Wang (eds.) (2019). (Vol. 129) 10:1–10:16.
- [ BibTeX ]
- [ URL ]
@inproceedings{angelini_et_al:LIPIcs:2019:10414, address = {Dagstuhl, Germany}, annote = {Keywords: Contact representations, Triangulations, Planar morphs, Schnyder woods}, author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Lozzo, Giordano Da and Roselli, Vincenzo}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, editor = {Barequet, Gill and Wang, Yusu}, keywords = {publication}, pages = {10:1–10:16}, publisher = {Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Morphing Contact Representations of Graphs.}, volume = 129, year = 2019 }

2018[ to top ]

On the structure of (pan, even hole)-free graphs Cameron, Kathie; Chaplick, Steven; Hoàng, Chính T. in Journal of Graph Theory (2018). 87(1) 108–129.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
A hole is a chordless cycle with at least four vertices. A pan is a graph that consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)-free graph can be decomposed by clique cutsets into essentially unit circular-arc graphs. This structure theorem is the basis of our O(nm)-time certifying algorithm for recognizing (pan, even hole)-free graphs and for our O(n2.5+nm)-time algorithm to optimally color them. Using this structure theorem, we show that the tree-width of a (pan, even hole)-free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 time the clique number.

@article{JGT:JGT22146, abstract = {A hole is a chordless cycle with at least four vertices. A pan is a graph that consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)-free graph can be decomposed by clique cutsets into essentially unit circular-arc graphs. This structure theorem is the basis of our O(nm)-time certifying algorithm for recognizing (pan, even hole)-free graphs and for our O(n2.5+nm)-time algorithm to optimally color them. Using this structure theorem, we show that the tree-width of a (pan, even hole)-free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 time the clique number.}, author = {Cameron, Kathie and Chaplick, Steven and Hoàng, Chính T.}, journal = {Journal of Graph Theory}, keywords = {publication}, number = 1, pages = {108–129}, title = {On the structure of (pan, even hole)-free graphs}, volume = 87, year = 2018 }
Approximation Schemes for Geometric Coverage Problems Chaplick, Steven; De, Minati; Ravsky, Alexander; Spoerhase, Joachim in Proc. 26th Annual European Symposium on Algorithms (ESA’18), LIPIcs, Y. Azar, H. Bast, G. Herman (eds.) (2018). (Vol. 112) 17:1–17:15.
- [ BibTeX ]
- [ URL ]
@inproceedings{conf/esa/ChaplickDRS18, author = {Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim}, booktitle = {Proc. 26th Annual European Symposium on Algorithms (ESA'18)}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, keywords = {publication}, pages = {17:1–17:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Approximation Schemes for Geometric Coverage Problems}, volume = 112, year = 2018 }
Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Graph Drawing and Network Visualization - 26th International Symposium, {GD} 2018, Barcelona, Spain, September 26-28, 2018, Proceedings, Lecture Notes in Computer Science, T. C. Biedl, A. Kerren (eds.) (2018). (Vol. 11282) 137–151.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $n$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $O(n) O(n)$. Then, we show that every $n$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $O(n^3) O(n^3)$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

@inproceedings{conf/gd/ChaplickLWZ18, abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $n$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $O(n) O(n)$. Then, we show that every $n$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $O(n^3) O(n^3)$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.}, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Graph Drawing and Network Visualization - 26th International Symposium, {GD} 2018, Barcelona, Spain, September 26-28, 2018, Proceedings}, editor = {Biedl, Therese C. and Kerren, Andreas}, keywords = {publication}, pages = {137–151}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends.}, volume = 11282, year = 2018 }
On some graphs with a unique perfect matching Chaplick, Steven; Fürst, Maximilian; Maffray, Frédéric; Rautenbach, Dieter in Information Processing Letters (2018). 139 60–63.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Combining known results it follows that deciding whether a given graph G of size m has a unique perfect matching as well as finding that matching if it exists, can be done in time O(m) if G is either a cograph, or a split graph, or a claw-free graph. We provide structural insights concerning the graphs with a unique perfect matching that belong to these three graph classes, which lead to simple linear time algorithms for the unique perfect matching problem.

@article{journals/ipl/ChaplickFMR18, abstract = {Combining known results it follows that deciding whether a given graph G of size m has a unique perfect matching as well as finding that matching if it exists, can be done in time O(m) if G is either a cograph, or a split graph, or a claw-free graph. We provide structural insights concerning the graphs with a unique perfect matching that belong to these three graph classes, which lead to simple linear time algorithms for the unique perfect matching problem.}, author = {Chaplick, Steven and Fürst, Maximilian and Maffray, Frédéric and Rautenbach, Dieter}, journal = {Information Processing Letters}, keywords = {publication}, pages = {60–63}, title = {On some graphs with a unique perfect matching}, volume = 139, year = 2018 }
Grid Intersection Graphs and Order Dimension Chaplick, Steven; Felsner, Stefan; Hoffmann, Udo; Wiechert, Veit in Order (2018). 35(2) 363–391.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.

@article{Chaplick2018, abstract = {We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.}, author = {Chaplick, Steven and Felsner, Stefan and Hoffmann, Udo and Wiechert, Veit}, journal = {Order}, keywords = {publication}, month = {jul}, number = 2, pages = {363–391}, title = {Grid Intersection Graphs and Order Dimension}, volume = 35, year = 2018 }
The Partial Visibility Representation Extension Problem Chaplick, Steven; Gu{\’{s}}piel, Grzegorz; Gutowski, Grzegorz; Krawczyk, Tomasz; Liotta, Giuseppe in Algorithmica (2018). 80(8) 2286–2323.
- [ BibTeX ]
- [ URL ]
@article{Chaplick2018, author = {Chaplick, Steven and Gu{\'{s}}piel, Grzegorz and Gutowski, Grzegorz and Krawczyk, Tomasz and Liotta, Giuseppe}, journal = {Algorithmica}, keywords = {publication}, month = {aug}, number = 8, pages = {2286–2323}, title = {The Partial Visibility Representation Extension Problem}, volume = 80, year = 2018 }
Placing your Coins on a Shelf Alt, Helmut; Buchin, Kevin; Chaplick, Steven; Cheong, Otfried; Kindermann, Philipp; Knauer, Christian; Stehn, Fabian in JoCG (2018). 9(1) 312–327.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We consider the problem of packing a family of disks on a shelf", that is, such that each disk touches the $x$-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in $O(n n)$ time, and provide an $O(n n)$-time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.

@article{journals/jocg/AltBCCKKS18, abstract = {We consider the problem of packing a family of disks on a shelf", that is, such that each disk touches the $x$-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in $O(n n)$ time, and provide an $O(n n)$-time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.}, author = {Alt, Helmut and Buchin, Kevin and Chaplick, Steven and Cheong, Otfried and Kindermann, Philipp and Knauer, Christian and Stehn, Fabian}, journal = {JoCG}, keywords = {publication}, number = 1, pages = {312–327}, title = {Placing your Coins on a Shelf}, volume = 9, year = 2018 }

2017[ to top ]

Max point-tolerance graphs Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halld{\’{o}}rsson, Bjarni V.; Halld{\’{o}}rsson, Magn{\’{u}}s M.; Hixon, Thomas; Stacho, Juraj in Discrete Applied Mathematics (2017). 216 84–97.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/dam/CatanzaroCFHHHS17, author = {Catanzaro, Daniele and Chaplick, Steven and Felsner, Stefan and Halld{\'{o}}rsson, Bjarni V. and Halld{\'{o}}rsson, Magn{\'{u}}s M. and Hixon, Thomas and Stacho, Juraj}, journal = {Discrete Applied Mathematics}, keywords = {publication}, pages = {84–97}, title = {Max point-tolerance graphs}, volume = 216, year = 2017 }
Threshold-coloring and unit-cube contact representation of planar graphs Alam, Md. Jawaherul; Chaplick, Steven; Fijavz, Gasper; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Toeniskoetter, Jackson in Discrete Applied Mathematics (2017). 216 2–14.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/dam/AlamCFKKPT17, author = {Alam, Md. Jawaherul and Chaplick, Steven and Fijavz, Gasper and Kaufmann, Michael and Kobourov, Stephen G. and Pupyrev, Sergey and Toeniskoetter, Jackson}, journal = {Discrete Applied Mathematics}, keywords = {publication}, pages = {2–14}, title = {Threshold-coloring and unit-cube contact representation of planar graphs}, volume = 216, year = 2017 }
Combinatorial Problems on H -graphs Chaplick, Steven; Zeman, Peter in Electronic Notes in Discrete Mathematics (2017). 61 223–229.
- [ BibTeX ]
- [ URL ]
@article{Chaplick_2017, author = {Chaplick, Steven and Zeman, Peter}, journal = {Electronic Notes in Discrete Mathematics}, keywords = {publication}, month = {aug}, note = {EUROCOMB 2017}, pages = {223–229}, publisher = {Elsevier {BV}}, title = {Combinatorial Problems on H -graphs}, volume = 61, year = 2017 }
The Complexity of Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Proc. Algorithms Data Struct. Symp. (WADS’17), F. Ellen, A. Kolokolova, J.-R. Sack (eds.) (2017). 265–276.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
It is well known that any graph admits a crossing-free straight-line drawing in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^3{\$}{\$} and that any planar graph admits the same even in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^2{\$}{\$} . For a graph G and {\$}{\$}d {\backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\$}{\$} , let {\$}{\$}{\backslash}rho ^1{\_}d(G){\$}{\$} denote the minimum number of lines in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^d{\$}{\$} that together can cover all edges of a drawing of G. For {\$}{\$}d=2{\$}{\$} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.

@inbook{Chaplick2017, abstract = {It is well known that any graph admits a crossing-free straight-line drawing in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^3{\$}{\$} and that any planar graph admits the same even in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^2{\$}{\$} . For a graph G and {\$}{\$}d {\backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\$}{\$} , let {\$}{\$}{\backslash}rho ^1{\_}d(G){\$}{\$} denote the minimum number of lines in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^d{\$}{\$} that together can cover all edges of a drawing of G. For {\$}{\$}d=2{\$}{\$} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.}, address = {Cham}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)}, editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger}, keywords = {publication}, pages = {265–276}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, year = 2017 }
On Vertex- and Empty-Ply Proximity Drawings Angelini, Patrizio; Chaplick, Steven; De Luca, Felice; Fiala, Ji{\v{r}}{\’i}; Han{\v{c}}l, Jaroslav; Heinsohn, Niklas; Kaufmann, Michael; Kobourov, Stephen; Kratochv{\’i}l, Jan; Valtr, Pavel in Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), LNCS, F. Frati, K.-L. Ma (eds.) (2017). (Vol. 10692) 24–37.
- [ Abstract ]
- [ BibTeX ]
We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. The vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. The main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. Then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings.

@inproceedings{10.1007/978-3-319-73915-1_3, abstract = {We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. The vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. The main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. Then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings.}, address = {Cham}, author = {Angelini, Patrizio and Chaplick, Steven and De Luca, Felice and Fiala, Ji{\v{r}}{\'i} and Han{\v{c}}l, Jaroslav and Heinsohn, Niklas and Kaufmann, Michael and Kobourov, Stephen and Kratochv{\'i}l, Jan and Valtr, Pavel}, booktitle = {Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {publication}, pages = {24–37}, publisher = {Springer International Publishing}, series = {LNCS}, title = {On Vertex- and Empty-Ply Proximity Drawings}, volume = 10692, year = 2017 }
On H-Topological Intersection Graphs Chaplick, Steven; T{\"o}pfer, Martin; Voborn{\’i}k, Jan; Zeman, Peter in Graph-Theoretic Concepts in Computer Science: 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, H. L. Bodlaender, G. J. Woeginger (eds.) (2017). 167–179.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Bir{\'o}, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph H. They naturally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. Our paper is the first study of the recognition and dominating set problems of this large collection of intersection classes of graphs.

@inbook{Chaplick2017, abstract = {Bir{\'o}, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph H. They naturally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. Our paper is the first study of the recognition and dominating set problems of this large collection of intersection classes of graphs.}, address = {Cham}, author = {Chaplick, Steven and T{\"o}pfer, Martin and Voborn{\'i}k, Jan and Zeman, Peter}, booktitle = {Graph-Theoretic Concepts in Computer Science: 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers}, editor = {Bodlaender, Hans L. and Woeginger, Gerhard J.}, keywords = {publication}, pages = {167–179}, publisher = {Springer International Publishing}, title = {On H-Topological Intersection Graphs}, year = 2017 }
Planar L-Drawings of Directed Graphs Chaplick, Steven; Chimani, Markus; Cornelsen, Sabine; Da Lozzo, Giordano; N{\"o}llenburg, Martin; Patrignani, Maurizio; Tollis, Ioannis G.; Wolff, Alexander in Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), LNCS, F. Frati, K.-L. Ma (eds.) (2017). (Vol. 10692) 465–478.
- [ Abstract ]
- [ BibTeX ]
We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. Motivated by this result, we focus on upward-planar L-drawings. We show that directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing are exactly those admitting a bitonic (resp. monotonically increasing) st-ordering. We give a linear-time algorithm that computes a bitonic (resp. monotonically increasing) st-ordering of a planar st-graph or reports that there exists none.

@inproceedings{10.1007/978-3-319-73915-1_36, abstract = {We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. Motivated by this result, we focus on upward-planar L-drawings. We show that directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing are exactly those admitting a bitonic (resp. monotonically increasing) st-ordering. We give a linear-time algorithm that computes a bitonic (resp. monotonically increasing) st-ordering of a planar st-graph or reports that there exists none.}, address = {Cham}, author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and N{\"o}llenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander}, booktitle = {Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {publication}, pages = {465–478}, publisher = {Springer International Publishing}, series = {LNCS}, title = {Planar L-Drawings of Directed Graphs}, volume = 10692, year = 2017 }
Ferrers dimension of grid intersection graphs Chaplick, Steven; Hell, Pavol; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei in Discrete Applied Mathematics (2017). 216 130–135.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/dam/ChaplickHOSU17, author = {Chaplick, Steven and Hell, Pavol and Otachi, Yota and Saitoh, Toshiki and Uehara, Ryuhei}, journal = {Discrete Applied Mathematics}, keywords = {publication}, pages = {130–135}, title = {Ferrers dimension of grid intersection graphs}, volume = 216, year = 2017 }
Placing your Coins on a Shelf Alt, Helmut; Buchin, Kevin; Chaplick, Steven; Cheong, Otfried; Kindermann, Philipp; Knauer, Christian; Stehn, Fabian in 28th International Symposium on Algorithms and Computation (ISAAC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Y. Okamoto, T. Tokuyama (eds.) (2017). (Vol. 92) 4:1–4:12.
- [ BibTeX ]
- [ URL ]
@inproceedings{conf/isaac/AltBCCKKS17, address = {Dagstuhl, Germany}, annote = {Keywords: packing problems, approximation algorithms, NP-hardness}, author = {Alt, Helmut and Buchin, Kevin and Chaplick, Steven and Cheong, Otfried and Kindermann, Philipp and Knauer, Christian and Stehn, Fabian}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, keywords = {publication}, pages = {4:1–4:12}, publisher = {Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Placing your Coins on a Shelf}, volume = 92, year = 2017 }
Beyond Outerplanarity Chaplick, Steven; Kryven, Myroslav; Liotta, Giuseppe; Löffler, Andre; Wolff, Alexander in Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), LNCS, F. Frati, K.-L. Ma (eds.) (2017). (Vol. 10692) 546–559.
- [ Abstract ]
- [ BibTeX ]
We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with nice convex drawings: outer k-planar graphs, where each edge is crossed by at most k other edges; and, outer k-quasi-planar graphs where no k edges can mutually cross.

@inproceedings{10.1007/978-3-319-73915-1_42, abstract = {We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with nice convex drawings: outer k-planar graphs, where each edge is crossed by at most k other edges; and, outer k-quasi-planar graphs where no k edges can mutually cross.}, address = {Cham}, author = {Chaplick, Steven and Kryven, Myroslav and Liotta, Giuseppe and Löffler, Andre and Wolff, Alexander}, booktitle = {Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {publication}, pages = {546–559}, publisher = {Springer International Publishing}, series = {LNCS}, title = {Beyond Outerplanarity}, volume = 10692, year = 2017 }

2016[ to top ]

Edge intersection graphs of L-shaped paths in grids Cameron, Kathie; Chaplick, Steven; Ho{\`{a}}ng, Ch{\’{\i}}nh T. in Discrete Applied Mathematics (2016). 210 185–194.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/dam/CameronCH16, author = {Cameron, Kathie and Chaplick, Steven and Ho{\`{a}}ng, Ch{\'{\i}}nh T.}, journal = {Discrete Applied Mathematics}, keywords = {publication}, pages = {185–194}, title = {Edge intersection graphs of L-shaped paths in grids}, volume = 210, year = 2016 }
The Partial Visibility Representation Extension Problem Chaplick, Steven; Guspiel, Grzegorz; Gutowski, Grzegorz; Krawczyk, Tomasz; Liotta, Giuseppe in Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science, Y. Hu, M. N{\"{o}}llenburg (eds.) (2016). (Vol. 9801) 266–279.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/gd/ChaplickGGKL16, author = {Chaplick, Steven and Guspiel, Grzegorz and Gutowski, Grzegorz and Krawczyk, Tomasz and Liotta, Giuseppe}, booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers}, editor = {Hu, Yifan and N{\"{o}}llenburg, Martin}, keywords = {publication}, month = {sep}, pages = {266–279}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {The Partial Visibility Representation Extension Problem}, volume = 9801, year = 2016 }
Simultaneous Orthogonal Planarity Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; {Da Lozzo}, Giordano; {Di Battista}, Giuseppe; Eades, Peter; Kindermann, Philipp; Kratochv{\’{\i}}l, Jan; Lipp, Fabian; Rutter, Ignaz in Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science, Y. Hu, M. N{\"{o}}llenburg (eds.) (2016). (Vol. 9801) 532–545.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/gd/AngeliniCCLBEKK16, author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and {Da Lozzo}, Giordano and {Di Battista}, Giuseppe and Eades, Peter and Kindermann, Philipp and Kratochv{\'{\i}}l, Jan and Lipp, Fabian and Rutter, Ignaz}, booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers}, editor = {Hu, Yifan and N{\"{o}}llenburg, Martin}, keywords = {publication}, month = {sep}, pages = {532–545}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Orthogonal Planarity}, volume = 9801, year = 2016 }
Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science, Y. Hu, M. N{\"{o}}llenburg (eds.) (2016). (Vol. 9801) 166–180.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/gd/ChaplickFLRVW16, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers}, editor = {Hu, Yifan and N{\"{o}}llenburg, Martin}, keywords = {publication}, month = {sep}, pages = {166–180}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 9801, year = 2016 }
Obstructing Visibilities with One Obstacle Chaplick, Steven; Lipp, Fabian; Park, Ji{-}Won; Wolff, Alexander in Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science, Y. Hu, M. N{\"{o}}llenburg (eds.) (2016). (Vol. 9801) 295–308.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/gd/ChaplickLPW16, author = {Chaplick, Steven and Lipp, Fabian and Park, Ji{-}Won and Wolff, Alexander}, booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers}, editor = {Hu, Yifan and N{\"{o}}llenburg, Martin}, keywords = {publication}, month = {sep}, pages = {295–308}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Obstructing Visibilities with One Obstacle}, volume = 9801, year = 2016 }
A note on concurrent graph sharing games Chaplick, Steven; Micek, Piotr; Ueckerdt, Torsten; Wiechert, Veit in Integers (2016). 16 Paper No. G1.
- [ BibTeX ]
- [ URL ]
@article{chaplick2016concurrent, author = {Chaplick, Steven and Micek, Piotr and Ueckerdt, Torsten and Wiechert, Veit}, journal = {Integers}, keywords = {publication}, pages = {Paper No. G1}, title = {A note on concurrent graph sharing games}, volume = 16, year = 2016 }

2015[ to top ]

Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree Chaplick, Steven; Fiala, Jir{\’{\i}}; van ’t Hof, Pim; Paulusma, Dani{\"{e}}l; Tesar, Marek in Theor. Comput. Sci. (2015). 590 86–95.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/tcs/ChaplickFHPT15, author = {Chaplick, Steven and Fiala, Jir{\'{\i}} and van 't Hof, Pim and Paulusma, Dani{\"{e}}l and Tesar, Marek}, journal = {Theor. Comput. Sci.}, keywords = {publication}, pages = {86–95}, title = {Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree}, volume = 590, year = 2015 }

2014[ to top ]

The vertex leafage of chordal graphs Chaplick, Steven; Stacho, Juraj in Discrete Applied Mathematics (2014). 168 14–25.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/dam/ChaplickS14, author = {Chaplick, Steven and Stacho, Juraj}, journal = {Discrete Applied Mathematics}, keywords = {publication}, pages = {14–25}, title = {The vertex leafage of chordal graphs}, volume = 168, year = 2014 }
Intersection Dimension of Bipartite Graphs Chaplick, Steven; Hell, Pavol; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei in Theory and Applications of Models of Computation - 11th Annual Conference, {TAMC} 2014, Chennai, India, April 11-13, 2014. Proceedings, Lecture Notes in Computer Science, T. V. Gopal, M. Agrawal, A. Li, S. B. Cooper (eds.) (2014). (Vol. 8402) 323–340.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/tamc/ChaplickHOSU14, author = {Chaplick, Steven and Hell, Pavol and Otachi, Yota and Saitoh, Toshiki and Uehara, Ryuhei}, booktitle = {Theory and Applications of Models of Computation - 11th Annual Conference, {TAMC} 2014, Chennai, India, April 11-13, 2014. Proceedings}, editor = {Gopal, T. V. and Agrawal, Manindra and Li, Angsheng and Cooper, S. Barry}, keywords = {publication}, pages = {323–340}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Intersection Dimension of Bipartite Graphs}, volume = 8402, year = 2014 }
Contact Representations of Planar Graphs: Extending a Partial Representation is Hard Chaplick, Steven; Dorbec, Paul; Kratochv{\’{\i}}l, Jan; Montassier, Micka{\"{e}}l; Stacho, Juraj in Graph-Theoretic Concepts in Computer Science - 40th International Workshop, {WG} 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, Lecture Notes in Computer Science, D. Kratsch, I. Todinca (eds.) (2014). (Vol. 8747) 139–151.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/wg/ChaplickDKMS14, author = {Chaplick, Steven and Dorbec, Paul and Kratochv{\'{\i}}l, Jan and Montassier, Micka{\"{e}}l and Stacho, Juraj}, booktitle = {Graph-Theoretic Concepts in Computer Science - 40th International Workshop, {WG} 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers}, editor = {Kratsch, Dieter and Todinca, Ioan}, keywords = {publication}, pages = {139–151}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Contact Representations of Planar Graphs: Extending a Partial Representation is Hard}, volume = 8747, year = 2014 }

2013[ to top ]

Threshold-Coloring and Unit-Cube Contact Representation of Graphs Alam, Md. Jawaherul; Chaplick, Steven; Fijavz, Gasper; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey in Graph-Theoretic Concepts in Computer Science - 39th International Workshop, {WG} 2013, L{\"{u}}beck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, A. Brandst{\"{a}}dt, K. Jansen, R. Reischuk (eds.) (2013). (Vol. 8165) 26–37.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/wg/AlamCFKKP13, author = {Alam, Md. Jawaherul and Chaplick, Steven and Fijavz, Gasper and Kaufmann, Michael and Kobourov, Stephen G. and Pupyrev, Sergey}, booktitle = {Graph-Theoretic Concepts in Computer Science - 39th International Workshop, {WG} 2013, L{\"{u}}beck, Germany, June 19-21, 2013, Revised Papers}, editor = {Brandst{\"{a}}dt, Andreas and Jansen, Klaus and Reischuk, R{\"{u}}diger}, keywords = {publication}, pages = {26–37}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Threshold-Coloring and Unit-Cube Contact Representation of Graphs}, volume = 8165, year = 2013 }
Equilateral L-Contact Graphs Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten in Graph-Theoretic Concepts in Computer Science - 39th International Workshop, {WG} 2013, L{\"{u}}beck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, A. Brandst{\"{a}}dt, K. Jansen, R. Reischuk (eds.) (2013). (Vol. 8165) 139–151.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/wg/ChaplickKU13, author = {Chaplick, Steven and Kobourov, Stephen G. and Ueckerdt, Torsten}, booktitle = {Graph-Theoretic Concepts in Computer Science - 39th International Workshop, {WG} 2013, L{\"{u}}beck, Germany, June 19-21, 2013, Revised Papers}, editor = {Brandst{\"{a}}dt, Andreas and Jansen, Klaus and Reischuk, R{\"{u}}diger}, keywords = {publication}, pages = {139–151}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Equilateral L-Contact Graphs}, volume = 8165, year = 2013 }
Planar Graphs as VPG-Graphs Chaplick, Steven; Ueckerdt, Torsten in J. Graph Algorithms Appl. (2013). 17(4) 475–494.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/jgaa/ChaplickU13, author = {Chaplick, Steven and Ueckerdt, Torsten}, journal = {J. Graph Algorithms Appl.}, keywords = {publication}, number = 4, pages = {475–494}, title = {Planar Graphs as VPG-Graphs}, volume = 17, year = 2013 }
Stabbing Polygonal Chains with Rays is Hard to Approximate Chaplick, Steven; Cohen, Elad; Morgenstern, Gila in Proceedings of the 25th Canadian Conference on Computational Geometry, {CCCG} 2013, Waterloo, Ontario, Canada, August 8-10, 2013 (2013).
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/cccg/ChaplickCM13, author = {Chaplick, Steven and Cohen, Elad and Morgenstern, Gila}, booktitle = {Proceedings of the 25th Canadian Conference on Computational Geometry, {CCCG} 2013, Waterloo, Ontario, Canada, August 8-10, 2013}, keywords = {publication}, publisher = {Carleton University, Ottawa, Canada}, title = {Stabbing Polygonal Chains with Rays is Hard to Approximate}, year = 2013 }
Extending Partial Representations of Circle Graphs Chaplick, Steven; Fulek, Radoslav; Klav{\’{\i}}k, Pavel in Graph Drawing - 21st International Symposium, {GD} 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, Lecture Notes in Computer Science, S. K. Wismath, A. Wolff (eds.) (2013). (Vol. 8242) 131–142.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/gd/ChaplickFK13, author = {Chaplick, Steven and Fulek, Radoslav and Klav{\'{\i}}k, Pavel}, booktitle = {Graph Drawing - 21st International Symposium, {GD} 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers}, editor = {Wismath, Stephen K. and Wolff, Alexander}, keywords = {publication}, pages = {131–142}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Extending Partial Representations of Circle Graphs}, volume = 8242, year = 2013 }
Edge Intersection Graphs of L-Shaped Paths in Grids Cameron, Kathie; Chaplick, Steven; Ho{\`{a}}ng, Ch{\’{\i}}nh T. in Electronic Notes in Discrete Mathematics (2013). 44 363–369.
- [ BibTeX ]
- [ URL ]
@article{DBLP:journals/endm/CameronCH13, author = {Cameron, Kathie and Chaplick, Steven and Ho{\`{a}}ng, Ch{\'{\i}}nh T.}, journal = {Electronic Notes in Discrete Mathematics}, keywords = {publication}, pages = {363–369}, title = {Edge Intersection Graphs of L-Shaped Paths in Grids}, volume = 44, year = 2013 }
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree Chaplick, Steven; Fiala, Jir{\’{\i}}; van ’t Hof, Pim; Paulusma, Dani{\"{e}}l; Tesar, Marek in Fundamentals of Computation Theory - 19th International Symposium, {FCT} 2013, Liverpool, UK, August 19-21, 2013. Proceedings, Lecture Notes in Computer Science, L. Gasieniec, F. Wolter (eds.) (2013). (Vol. 8070) 121–132.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/fct/ChaplickFHPT13, author = {Chaplick, Steven and Fiala, Jir{\'{\i}} and van 't Hof, Pim and Paulusma, Dani{\"{e}}l and Tesar, Marek}, booktitle = {Fundamentals of Computation Theory - 19th International Symposium, {FCT} 2013, Liverpool, UK, August 19-21, 2013. Proceedings}, editor = {Gasieniec, Leszek and Wolter, Frank}, keywords = {publication}, pages = {121–132}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree}, volume = 8070, year = 2013 }

2012[ to top ]

Planar Graphs as VPG-Graphs Chaplick, Steven; Ueckerdt, Torsten in Graph Drawing - 20th International Symposium, {GD} 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, Lecture Notes in Computer Science, W. Didimo, M. Patrignani (eds.) (2012). (Vol. 7704) 174–186.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/gd/ChaplickU12, author = {Chaplick, Steven and Ueckerdt, Torsten}, booktitle = {Graph Drawing - 20th International Symposium, {GD} 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers}, editor = {Didimo, Walter and Patrignani, Maurizio}, keywords = {publication}, pages = {174–186}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Planar Graphs as VPG-Graphs}, volume = 7704, year = 2012 }
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill Chaplick, Steven; Jel{\’{\i}}nek, V{\’{\i}}t; Kratochv{\’{\i}}l, Jan; Vyskocil, Tom{\’{a}}s in Graph-Theoretic Concepts in Computer Science - 38th International Workshop, {WG} 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers, Lecture Notes in Computer Science, M. C. Golumbic, M. Stern, A. Levy, G. Morgenstern (eds.) (2012). (Vol. 7551) 274–285.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/wg/ChaplickJKV12, author = {Chaplick, Steven and Jel{\'{\i}}nek, V{\'{\i}}t and Kratochv{\'{\i}}l, Jan and Vyskocil, Tom{\'{a}}s}, booktitle = {Graph-Theoretic Concepts in Computer Science - 38th International Workshop, {WG} 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers}, editor = {Golumbic, Martin Charles and Stern, Michal and Levy, Avivit and Morgenstern, Gila}, keywords = {publication}, pages = {274–285}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill}, volume = 7551, year = 2012 }

2011[ to top ]

Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid Chaplick, Steven; Cohen, Elad; Stacho, Juraj in Graph-Theoretic Concepts in Computer Science - 37th International Workshop, {WG} 2011, Tepl{\’{a}} Monastery, Czech Republic, June 21-24, 2011. Revised Papers, Lecture Notes in Computer Science, P. Kolman, J. Kratochv{\’{\i}}l (eds.) (2011). (Vol. 6986) 319–330.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/wg/ChaplickCS11, author = {Chaplick, Steven and Cohen, Elad and Stacho, Juraj}, booktitle = {Graph-Theoretic Concepts in Computer Science - 37th International Workshop, {WG} 2011, Tepl{\'{a}} Monastery, Czech Republic, June 21-24, 2011. Revised Papers}, editor = {Kolman, Petr and Kratochv{\'{\i}}l, Jan}, keywords = {publication}, pages = {319–330}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid}, volume = 6986, year = 2011 }

2010[ to top ]

From Path Graphs to Directed Path Graphs Chaplick, Steven; Gutierrez, Marisa; L{\’{e}}v{\^{e}}que, Benjamin; Tondato, Silvia B. in Graph Theoretic Concepts in Computer Science - 36th International Workshop, {WG} 2010, Zar{\’{o}}s, Crete, Greece, June 28-30, 2010 Revised Papers, Lecture Notes in Computer Science, D. M. Thilikos (ed.) (2010). (Vol. 6410) 256–265.
- [ BibTeX ]
- [ URL ]
@inproceedings{DBLP:conf/wg/ChaplickGLT10, author = {Chaplick, Steven and Gutierrez, Marisa and L{\'{e}}v{\^{e}}que, Benjamin and Tondato, Silvia B.}, booktitle = {Graph Theoretic Concepts in Computer Science - 36th International Workshop, {WG} 2010, Zar{\'{o}}s, Crete, Greece, June 28-30, 2010 Revised Papers}, editor = {Thilikos, Dimitrios M.}, keywords = {publication}, pages = {256–265}, series = {Lecture Notes in Computer Science}, title = {From Path Graphs to Directed Path Graphs}, volume = 6410, year = 2010 }

Preprints / Tech Reports