# Juraj Stacho

Rm 308A Mudd Bldg
IEOR Department
Columbia University
500 West 120th Street
New York, NY 10027
United States

Tel: (+1) 212-854-0191
Fax: (+1) 212-854-8103

stacho[at]cs.toronto.edu

My name is Juraj Stacho [ɪuraɪ stɑxo] (יוראי סטכו) {юрай стахо}. I work as a post-doctoral researcher at Columbia University in the Department of Industrial Engineering and Operations Research in the School of Engineering and Applied Science in New York, USA.

## Bio

2013-14
Post-doc with Prof. Maria Chudnovsky in the Department of Industrial Engineering and Operations Research at Columbia University in New York, USA.
2011-13
2010-11
2010
2009
Post-doc with Prof. Derek Corneil in the Department of Computer Science of the University of Toronto in Toronto, ON, Canada.
2008-09
Post-doc with Prof. Michel Habib in the LIAFA laboratory of the University of Paris 7 - Paris Diderot in Paris, France.
2005-08
PhD. degree in Computing Science under the supervision of Prof. Pavol Hell at the Simon Fraser University (SFU) in Burnaby, BC, Canada.
2000-05

## Research

My academic interests are: Algorithmic and Structural Graph Theory, Combinatorics and Discrete Optimization, and Algorithmic Complexity. In particular, I am interested in efficient algorithms for combinatorial and optimization problems on structured classes of graphs.
Currently I am working with Prof. Maria Chudnovsky on structual problems on graph. For more details, see my CV in English (PDF) or English (Text) or French or simply Print this page.

### Publications

1. M. Francis, P. Hell, J. Stacho: Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, submitted.
2. B. Martin, J. Stacho: Constraint satisfaction with counting quantifiers, submitted.
3. M. Chudnovsky, P. Maceli, J. Stacho, M. Zhong: 4-coloring P6-free graphs with no induced 5-cycles, submitted.
4. A. Atminas, R. Brignall, N. Korpelainen, V. V. Lozin, J. Stacho: Minimal Classes of Bipartite Graphs of Unbounded Clique-width.
5. S. Chaplick, P. Dorbec, J. Kratochvíl, M. Montassier, J. Stacho: Contact Representations of Planar Graph: Rebuilding is Hard, In: Graph-Theoretic Concepts in Computer Science (WG 2014), Lecture Notes in Computer Science, to appear.
6. R. Brignall, V. V. Lozin, J. Stacho: Bichain graphs: geometric model and universal graphs, submitted.
7. D. Catanzaro, S. Chaplick, S. Felsner, B. V. Halldórsson, M. M. Halldórsson, T. Hixon, J. Stacho: Max Point-Tolerance Graphs, submitted.
8. B. Martin, J. Stacho: Constraint Satisfaction with Counting Quantifiers 2, In: Computer Science - Theory and Applications (CSR 2014), Lecture Notes in Computer Science, to appear (see also arXiv:1312.7605)
9. D. Corneil, J. Stacho: Vertex ordering characterizations of graphs of bounded asteroidal number, Journal of Graph Theory (2014+).
10. M. Francis, P. Hell, J. Stacho: Blocking quadruple: a new obstruction to circular-arc graphs, SIAM Journal on Discrete Mathematics 28 (2014), pp. 631-655 - journal version of [9]
11. K. K. Dabrowski, V. V. Lozin, J. Stacho: Stable-Π partitions of graphs, Discrete Applied Mathematics (2013+).
12. M. Francis, P. Hell, J. Stacho: Obstructions to chordal circular-arc graphs of small independence number, Electronic Notes in Discrete Mathematics 44 (2013), pp. 75-81
13. M. Habib, J. Stacho: Unique perfect phylogeny is intractable, Theoretical Computer Science 476 (2013), pp. 47-66. DOI: 10.1016/j.tcs.2012.12.048 - journal version of [18].
14. S. Chaplick, J. Stacho: The vertex leafage of chordal graphs, Discrete Applied Mathematics (2013). DOI: 10.1016/j.dam.2012.12.006.
15. M. Adamaszek, J. Stacho: Algorithmic complexity of finding cross-cycles in flag complexes, In: Proceedings of the 2012 Symposium on Computational Geometry (SoCG 2012), pp. 51-60. DOI: 10.1145/2261250.2261258.
1. F. Madelaine, B. Martin, J. Stacho: Constraint satisfaction with counting quantifiers, In: Computer Science - Theory and Applications (CSR 2012), Lecture Notes in Computer Science 7353/2012, pp. 253-265. DOI: 10.1007/978-3-642-30642-6.
2. J. Stacho: 3-colouring AT-free graphs in polynomial time, Algorithmica 64 (2012), pp. 384-399. DOI: 10.1007/s00453-012-9624-8 - journal version of [20].
3. M. Groshaus, P. Hell, J. Stacho: On edge-sets of bicliques in graphs (corrected version -- an error in Theorem 11 was fixed), Discrete Applied Mathematics 160 (2012), pp. 2698-2708.
4. M. Habib, J. Stacho: Reduced clique graphs of chordal graphs, European Journal of Combinatorics 33 (2012), pp. 712-735.
5. S. Chaplick, E. Cohen, J. Stacho: Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid, In: Graph-Theoretic Concepts in Computer Science (WG 2011), Lecture Notes in Computer Science 6986/2011, pp. 319-330.
6. M. Habib, J. Stacho: Unique perfect phylogeny is NP-hard, In: Combinatorial Pattern Matching (CPM 2011), Lecture Notes in Computer Science 6661/2011, pp. 132-146 (also see here for extended version).
7. T. Feder, P. Hell, D.G. Schell, J. Stacho: Dichotomy for tree-structured trigraph list homomorphism problems, Discrete Applied Mathematics 159 (2011), pp. 1217-1224 (also see here for extended version).
8. J. Stacho: 3-colouring AT-free graphs in polynomial time, In: Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science 6507/2010, pp. 144-155.
9. M. Habib, J. Stacho: Polynomial-time algorithm for the leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300.
10. M. Habib, J. Stacho: A decomposition theorem for chordal graphs and its applications, In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes in Discrete Mathematics 34 (2009), pp. 561-565.
11. M. Habib, J. Stacho: Linear algorithms for chordal graphs of bounded directed vertex leafage, In: DIMAP Workshop on Algorithmic Graph Theory, Electronic Notes in Discrete Mathematics 32 (2009), pp. 99-108.
12. P. Hell, A. Raspaud, J. Stacho: On injective colourings of chordal graphs, In: LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science 4957/2008, pp. 520-530.
13. J. Stacho: On 2-subcolourings of chordal graphs, In: LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science 4957/2008, pp. 544-554.
14. J. Stacho: On ${P}_{4}$-transversals of chordal graphs, Discrete Mathematics 308 (2008), pp. 5548-5554.
15. T. Ekim, P. Hell, J. Stacho, D. de Werra: Polarity of chordal graphs, Discrete Applied Mathematics 156 (2008), pp. 2469-2479.

### Manuscripts in preparation

1. D. Corneil, J. Stacho: Atomic structure, hyperbolicity, and recognition of AT-free graphs with no induced 4-cycles.
2. M. Habib, J. G. Linn, J. Stacho: On the alternating linear extension and related problems.

## Teaching

• #### Spring 2014

IEOR 4004
(Introduction to OR - deterministic models)

• Lectures
• Mon 19:10-20:25 in 327 Mudd
• Wed 19:10-20:25 in 327 Mudd
• Office hours
• Tue 1pm-2pm in 308A Mudd

• Course material: Slides:
• #### Fall 2013

IEOR 4004
(Introduction to OR - deterministic models)

• Lectures
• Tue 10:10-11:25 in NWC 501
• Thu 10:10-11:25 in NWC 501
• Office hours
• Tue 12-1pm in 308A Mudd

• ... see CourseWorks for more details
• #### Spring 2013

CS 137 (Discrete Mathematics and its Applications 2)
• Lecture Feb. 11 lecture notes
• Lecture Feb. 14 lecture notes
• Lecture Feb. 18 lecture notes
• Lecture Feb. 21 lecture notes (for both lectures)
• Coursework #3 (due Feb. 25)
• #### Spring 2012

MA 252 (Combinatorial Optimisation)
• Lecture Jan. 23 - slides/lecture notes
• Lecture Jan. 25 - slides/lecture notes
• Lecture Jan. 27 - slides/lecture notes
• #### Fall 2011

MA 241 (Combinatorics)
• Lecture Oct. 26 - slides
• Lecture Oct. 31 - slides
• Lecture Nov. 1 - slides
• #### Fall 2007

MACM 101
• Lecture Oct. 30 - slides
• Lecture Nov. 1 - slides
• #### Fall 2006

MACM 101
• Tutorials:
Mon 10:30-11:20 AQ5037
11:30-12:20 WMC2503
12:30-13:20 AQ5049
Wed 9:30-10:20 ASB9705
11:30-12:20 AQ5016
12:30-13:20 AQ4120
Fri 11:30-12:20 AQ5030
12:30-13:20 WMC2503
• No Office hours
• Course webpage
• #### Spring 2006

MACM 101
• Tutorials:
Tue 9:30-10:30 AQ5118
10:30-11:30 AQ2120
11:20-12:30 WMC2503
Th 10:30-11:30 AQ5008
11:30-12:30 AQ5008
• Office hours:
Wed 3:30-4:30 L9014
Thu 3:30-4:30 L9014
• Course webpage
• #### Fall 2005

CMTP 120 Surrey Labs
• We 9:30-1:20, Surrey 305a
Th 9:30-1:20, Surrey 650
• Labs webpage

## Coding

Some recent coding I have done in my spare time, mainly in Javascript to explore HTML 5 and CSS 3 for client-side in-browser programming (very convenient for simple projects and quick deployment on the web)

### Curve plotting tool (click on the link)

Features:
• Produces scalable graphics
• Export to SVG, EPS, and PDF
Function plotting tool (older version)

### Graph drawing tool (click on the link and try examples)

Usage:
1. `graph.html?type=matrix&data=...`
2. `graph.html?type=graph6&data=...`
3. `graph.html?!...`

An adjacency matrix or adjacency list can be also loaded from a local file by clicking on `Load Matrix` or `Load Adj/List`. This requires the browser to support the File API (some browsers such as IE 9- do not support this)

Example files: sg4c.txt (matrix) sg3.lst (adjacency list)

Notes:
• if `type=matrix` then `data=` is followed by a 0-1 encoding of a square adjacency matrix of a graph; each row is separated by '-', example: `0001-0010-1001-1100`
• if `type=graph6` then `data=` is followed by a graph6 encoding of an undirected graph
• if `graph.html` followed by `?!` then the rest of the URL is an internal encoding of a graph (similar to graph6 but made only using safe characters)