my photograph

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.

Last modified:


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 P4-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.

Theses


Teaching


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)