Research Interests
- Graph theory
- Algorithms
- Discrete geometry
Papers
Distinguishing classes of intersection graphs of homothets or similarities of two convex disks
39th International Symposium on Computational Geometry, SoCG 2023, Leibniz International Proceedings in Informatics (LIPIcs) 258, 2:1–16, 2023
|
Coloring polygon visibility graphs and their generalizations
Journal of Combinatorial Theory, Series B 161, 268–300, 2023; preliminary version in: 37th International Symposium on Computational Geometry, SoCG 2021, Leibniz International Proceedings in Informatics (LIPIcs) 189, 29:1–16, 2021
|
Approximating pathwidth for graphs of small treewidth
ACM Transactions on Algorithms 19, 16:1–19, 2023; preliminary version in: 32nd Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2021, 1965–1976, 2021
|
A solution to Ringel's circle problem
38th International Symposium on Computational Geometry, SoCG 2022, Leibniz International Proceedings in Informatics (LIPIcs) 224, 33:1–14, 2022
|
Clustered 3-colouring graphs of bounded degree
Combinatorics, Probability and Computing 31, 123–135, 2022
|
Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
Journal of Combinatorial Theory, Series B 152, 353–378, 2022
|
Subexponential-time algorithms for finding large induced sparse subgraphs
Algorithmica 83, 2634–2650, 2021; preliminary version in: 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Leibniz International Proceedings in Informatics (LIPIcs) 148, 23:1–11, 2019
|
Sparse Kneser graphs are Hamiltonian
Journal of the London Mathematical Society 103, 1253–1275, 2021; preliminary version in: 50th Annual ACM SIGACT Symposium on the Theory of Computing, STOC 2018, 912–919, 2018
|
Coloring and maximum weight independent set of rectangles
32nd Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2021, 860–868, 2021
|
Planar graphs have bounded nonrepetitive chromatic number
Advances in Combinatorics 2020, 5:1–11, 2020
|
Outerstring graphs are χ-bounded
SIAM Journal on Discrete Mathematics 33, 2181–2199, 2019; preliminary version in: 30th Annual Symposium on Computational Geometry, SoCG 2014, 136–143, 2014
|
Coloring curves that cross a fixed curve
Discrete and Computational Geometry 61, 830–851, 2019; preliminary version in: 33rd International Symposium on Computational Geometry, SoCG 2017, Leibniz International Proceedings in Informatics (LIPIcs) 77, 56:1–15, 2017
|
Dimension of posets with planar cover graphs excluding two long incomparable chains
Journal of Combinatorial Theory, Series A 164, 1–23, 2019
|
Common tangents of two disjoint polygons in linear time and constant workspace
ACM Transactions on Algorithms 15, 12:1–21, 2018; preliminary version: Outer common tangents and nesting of convex hulls in linear time and constant workspace, 24th Annual European Symposium on Algorithms, ESA 2016, Leibniz International Proceedings in Informatics (LIPIcs) 57, 4:1–15, 2016
|
Dimension and cut vertices: an application of Ramsey theory
Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham, 187–199, 2018
|
On-line approach to off-line coloring problems on graphs with geometric representations
Combinatorica 37, 1139–1179, 2017; preliminary version: Coloring relatives of interval overlap graphs via on-line games, 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Lecture Notes in Computer Science 8572, 738–750, 2014
|
Extending partial representations of trapezoid graphs
43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, Lecture Notes in Computer Science 10520, 358–371, 2017
|
Graph sharing game and the structure of weighted graphs with a forbidden subdivision
Journal of Graph Theory 85, 22–50, 2017
|
On the Beer index of convexity and its variants
Discrete and Computational Geometry 57, 179–214, 2017; preliminary version in: 31st International Symposium on Computational Geometry, SoCG 2015, Leibniz International Proceedings in Informatics (LIPIcs) 34, 406–420, 2015
|
Minors and dimension
Journal of Combinatorial Theory, Series B 122, 668–689, 2017; preliminary version in: 26th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2015, 1698–1707, 2015
|
Graph drawings with one bend and few slopes
12th Latin American Symposium on Theoretical Informatics, LATIN 2016, Lecture Notes in Computer Science 9644, 549–561, 2016
|
Decomposition of multiple packings with subquadratic union complexity
Combinatorics, Probability and Computing 25, 145–153, 2016
|
Tree-width and dimension
Combinatorica 36, 431–450, 2016
|
New bounds on the maximum number of edges in k-quasi-planar graphs
Computational Geometry: Theory and Applications 50, 24–33, 2015; preliminary version in: 21st International Symposium on Graph Drawing, GD 2013, Lecture Notes in Computer Science 8242, 95–106, 2013
|
Triangle-free geometric intersection graphs with no large independent sets
Discrete and Computational Geometry 53, 221–225, 2015
|
Coloring triangle-free rectangle overlap graphs with O(log log n) colors
Discrete and Computational Geometry 53, 199–220, 2015; preliminary version: Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors, 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, Lecture Notes in Computer Science 8165, 333–344, 2013
|
Coloring intersection graphs of arc-connected sets in the plane
Discrete and Computational Geometry 52, 399–415, 2014
|
An extremal problem on crossing vectors
Journal of Combinatorial Theory, Series A 128, 41–55, 2014
|
Triangle-free intersection graphs of line segments with large chromatic number
Journal of Combinatorial Theory, Series B 105, 6–10, 2014
|
Outerplanar graph drawings with few slopes
Computational Geometry: Theory and Applications 47, 614–624, 2014; preliminary version in: 18th Annual International Conference on Computing and Combinatorics, COCOON 2012, Lecture Notes in Computer Science 7434, 323–334, 2012
|
Triangle-free geometric intersection graphs with large chromatic number
Discrete and Computational Geometry 50, 714–726, 2013
|
Extending partial representations of function graphs and permutation graphs
20th Annual European Symposium on Algorithms, ESA 2012, Lecture Notes in Computer Science 7501, 671–682, 2012
|
Parity in graph sharing games
Discrete Mathematics 312, 1788–1795, 2012
|
A graph-grabbing game
Combinatorics, Probability and Computing 20, 623–629, 2011
|
A simple representation of subwords of the Fibonacci word
Information Processing Letters 110, 956–960, 2010
|
Short CV
2008 | MSc (computer science) | Uniwersytet Jagielloński | Kraków, Poland |
2012 | PhD (computer science) | Uniwersytet Jagielloński | Kraków, Poland |
2013–2014 | Postdoctoral fellowship (12 months) | École Polytechnique Fédérale de Lausanne | Lausanne, Switzerland |
2014 | "Mobilność Plus" research fellowship (6 months) | Univerzita Karlova v Praze | Praha, Czechia |
2014–2015 | Visiting assistant professor (9 months) | Georgia Institute of Technology | Atlanta, USA |
2017 | Habilitation (computer science) | Uniwersytet Jagielloński | Kraków, Poland |
2017–2018 | Gastprofessor (6 months) | Technische Universität Berlin | Berlin, Germany |
- Home
- Algorithmics Research Group
- Foundations of Computer Science
- Faculty of Mathematics and Computer Science
- Contact
- Satori
- Reports on Mathematical Logic
- Forum TCS
- UsosWeb
- Informatyka na szlaku
- Photos
- People
- Bartłomiej Bosek
- Marcin Briański
- Iwona Cieślik
- Jan Derbisz
- Andrzej Dorobisz
- Lech Duraj
- Monika Gillert
- Katarzyna Grygiel
- Grzegorz Gutowski
- Grzegorz Herman
- Pawel M. Idziak
- Piotr Kawałek
- Marcin Kozik
- Jakub Kozik
- Tomasz Krawczyk
- Jacek Krzaczkowski
- Xuân La
- Agnieszka Łupińska
- Piotr Micek
- Jonathan Narboni
- Andrzej Pezarski
- Bartosz Podkanowicz
- Adam Polak
- Krzysztof Potępa
- Wojciech Szpankowski
- Maciej Ślusarek
- Jan Tułowiecki
- Krzysztof Turowski
- Bartosz Walczak
- Michał Wrona
- Marek Zaionc
- Former colleagues