Advertisement
Published in:
2010 | OriginalPaper | Chapter
Structural and Complexity Aspects of Line Systems of Graphs
Authors : Jozef Jirásek, Pavel Klavík
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study line systems in metric spaces induced by graphs. A line is a subset of vertices defined by a relation of betweenness.
We show that the class of all graphs having exactly
k
different lines is infinite if and only if it contains a graph with a bridge. We also study lines in random graphs—a random graph almost surely has
$n \choose 2$
different lines and no line containing all the vertices.
We call a pair of graphs isolinear if their line systems are isomorphic. We prove that deciding isolinearity of graphs is polynomially equivalent to the Graph Isomorphism Problem.
Similarly to the Graph Reconstruction Problem, we question the reconstructability of graphs from their line systems. We present a polynomial-time algorithm which constructs a tree from a given line system. We give an application of line systems: This algorithm can be extended to decide the existence of an embedding of a metric space into a tree metric and to construct this embedding if it exists.