• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Extending Partial Representations of Graphs / Extending Partial Representations of Graphs

Klavík, Pavel January 2012 (has links)
In this thesis, we study geometric intersection representations of graphs. For a fixed class, the well-known recognition problem asks whether a given graph belongs to this class. We study a generalization of this problem called partial representation extension. Its input consists of a graph with a partial representation, so a part of the graph is pre-drawn. The problems asks whether this partial representation can be extended to a representation of the entire graph. We study this problem for classes of interval graphs, proper interval graphs, unit interval graphs and chordal graphs (in the setting of subtrees-in-tree representations). We give linear-time algorithms for the first two classes and an almost quadratic-time algorithm for unit interval graphs. For chordal graphs, we consider different versions of the problem and show that almost all cases are NP-complete. Even though the classes of proper and unit interval graphs are known to be equal, the partial representation extension problem distinguishes them. For unit interval graphs, it poses additional restrictions concerning precise positions of intervals, and we describe a new structure of unit interval representations to deal with this. 1

Page generated in 0.1821 seconds