Sobre Grafos EPG e Imersões de Árvores em Grades

Abstract

In this work, we show that the graphs in which every block is B1-EPG and every cut vertex is universal in the blocks to which it belongs, are B2-EPG. We extend the proof to show that cactus graphs are B1-EPG. We also show a linear time algorithm to build L-EPG models of graphs in which every block is L-EPG and every cut vertex is universal in the blocks to which it belongs, concluding that the block graphs are L-EPG. The last result provides an alternative x-EPG representation for trees. Furthermore, we present an algorithm to embed a tree T with ∆(T)≤ 4 in a rectangular grid, so that the maximum number of bends in all paths of T is minimized. We also describe how to build s-models with k bends, having the minimum number of vertices possible for any given k 0. Furthermore, the s-models produced by our algorithm were employed to build EPG models of VPT ∩ EPT graphs, providing an upper bound on the bend-number of such graphs. Finally, we introduce a new class of graphs, EPGt, and provide a characterization of representations with at most one bend of cliques and cycles of 4 vertices in these grids, extending the analogous results of EPG graphs.