Structural Graph Theory deals with establishing results that characterize various properties of graphs, and utilizes them in the design of efficient algorithms and other applications. Typical topics in this area are graph minors and treewidth, modular decomposition and clique-width, characterization of graph families by forbidden configurations.
Sample publications:
- V.V. Lozin. Boundary classes of planar graphs. Combinatorics, Probability and Computing, 17: 287 - 295, 2008.
- V.V. Lozin, J. Volz. The clique-width of bipartite graphs in monogenic classes. International Journal of Foundations of Computer Science, 19: 477 - 494, 2008.
- V.V. Lozin, D. Rautenbach. The Relative Clique-Width of a Graph . Journal of Combinatorial Theory B, 95: 846 - 858, 2007.
- D. Christofides, Pair lengths of product graphs. Discrete Mathematics, 306: 2111-2114, 2006.
- A. Brandstädt, J. Engelfriet, Hoang-Oanh Le and V.V. Lozin. Clique-Width for Four-Vertex Forbidden Subgraphs. Theory of Computing Systems, 34: 561 - 590, 2006.
- A. Czumaj, M. M. Halldórsson, A. Lingas, and J. Nilsson. Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth. Information Processing Letters, 94(2): 49 - 53, 2005.
- A. Brandstädt, Peter L. Hammer, Van Bang Le and V.V. Lozin. Bisplit graphs. Discrete Mathematics, 299: 11 - 32, 2005.
- V.V. Lozin, D. Rautenbach. On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Mathematics, 18: 195 - 206, 2004.
- A. Brandstädt and V.V. Lozin. On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria, 67: 273 - 281, 2003.
- V.V. Lozin. Bipartite Graphs without a skew star. Discrete Mathematics, 257: 83 - 100, 2002.
