Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649072 | Discrete Mathematics | 2007 | 8 Pages |
Abstract
In this paper it is shown that a class of almost-median graphs that includes all planar almost-median graphs can be recognized in O(mlogn)O(mlogn) time, where n denotes the number of vertices and m the number of edges. Moreover, planar almost-median graphs can be recognized in linear time. As a key auxiliary result we prove that all bipartite outerplanar graphs are isometric subgraphs of the hypercube and that the embedding can be effected in linear time.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wilfried Imrich, Alenka Lipovec, Iztok Peterin, Petra Žigert,