Mathew C. Francis

Assistant Professor
Computer Science Unit
Indian Statistical Institute, Chennai Centre

email:

Research Interests: Algorithmic Graph Theory, Geometric Intersection Graphs.

Ph.D. Thesis - “Intersection graphs of boxes and cubes” (pdf)

Publications

In journals:

Boxicity and Maximum Degree, with L. Sunil Chandran and Naveen Sivadasan, Journal of Combinatorial Theory, Series B, 98(2):443–445, 2008.

On the Cubicity of Interval Graphs, with L. Sunil Chandran and Naveen Sivadasan, Graphs and Combinatorics, 25(2):169–179, 2009.

Boxicity of Halin Graphs, with L. Sunil Chandran and Santhosh Suresh, Discrete Mathematics, 309(10):3233–3237, 2009.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes, with L. Sunil Chandran and Naveen Sivadasan, Algorithmica, 56(2):129–140, 2010.

Non-contractible Non-edges in 2-connected Graphs, with Anita Das, Rogers Mathew and N. Sadagopan, Information Processing Letters, 110(23), 1044–1048, 2010.

Boxicity of Leaf Powers, with L. Sunil Chandran and Rogers Mathew, Graphs and Combinatorics, 27(1):61–72, 2011.

Chordal Bipartite Graphs with High Boxicity, with L. Sunil Chandran and Rogers Mathew, Graphs and Combinatorics, 27(3):353–362, 2011.

Cubicity and Bandwidth, with L. Sunil Chandran and Naveen Sivadasan, Graphs and Combinatorics, 29(1):45–69, 2013.

Segment Representation of a Subclass of Co-planar Graphs, with Jan Kratochvíl and Tomáš Vyskočil, Discrete Mathematics, 312(10):1815–1818, 2012.

Recognition and Characterization of Chronological Interval Digraphs, with Sandeep Das, Pavol Hell and Jing Huang, The Electronic Journal of Combinatorics, 20(3) (2013) #P5.

The Maximum Clique Problem in Multiple Interval Graphs, with Daniel Gonçalves and Pascal Ochem, Algorithmica, 71(4):812–836, 2015.

Blocking Quadruple: A New Obstruction to Circular-Arc Graphs, with Pavol Hell and Juraj Stacho, SIAM Journal on Discrete Mathematics, 28(2):631–655, 2014.

Strong Chromatic Index of Chordless Graphs, with Manu Basavaraju, Journal of Graph Theory, 80(1):58–68, 2015.

Partially Polynomial Kernels for Set Cover and Test Cover, with Manu Basavaraju, M. S. Ramanujan and Saket Saurabh, SIAM Journal on Discrete Mathematics, 30(3):1401–1423, 2016.

VPG and EPG Bend-numbers of Halin Graphs, with Abhiruk Lahiri, Discrete Applied Mathematics, 215:95–105, 2016.

Uniquely Restricted Matchings in Interval Graphs, with Dalu Jacob and Satyabrata Jana, accepted for publication in SIAM Journal on Discrete Mathematics.

In conferences:

On the Cubicity of Interval Graphs, with L. Sunil Chandran and Naveen Sivadasan, EuroComb'07, September 2007, Seville, Spain.

Representing Graphs as the Intersection of Axis Parallel Cubes, with L. Sunil Chandran and Naveen Sivadasan, MCDES 2008, May 2008, Bangalore.

On the Cubicity of AT-Free Graphs and Circular-Arc Graphs, with L. Sunil Chandran and Naveen Sivadasan, Graph Theory, Computational Intelligence and Thought, September 2008, Israel.

Chordal Bipartite Graphs with High Boxicity, with L. Sunil Chandran and Rogers Mathew, JCCGG 2009, November 2009, Kanazawa, Japan.

Contact Representations of Planar Graphs with Cubes, with Stefan Felsner, SoCG 2011, June 2011, Paris.

The Maximum Clique Problem in Multiple Interval Graphs, with Daniel Gonçalves and Pascal Ochem, WG 2012, June 2012, Jerusalem.

Obstructions to Chordal Circular-Arc Graphs, with Pavol Hell and Juraj Stacho, LAGOS 2013, April 2013, Playa del Carmen, Mexico.

Partially Polynomial Kernels for Set Cover and Test Cover, with Manu Basavaraju, M. S. Ramanujan and Saket Saurabh, FSTTCS 2013, December 2013, Guwahati, India.

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, with Pavol Hell and Juraj Stacho, SODA 2015, January 2015, San Diego.