Block graph

Block graphs are chordal, distance-hereditary, and geodetic. The distance-hereditary graphs are the graphs in which every two induced paths between the same two vertices have the same length, a weakening of the characterization of block graphs as having at most one induced path between every two vertices. Because both the chordal graphs and the distance-hereditary graphs are subclasses of the perfect graphs, block graphs are perfect.

Every tree, cluster graph, or windmill graph is a block graph.

Every block graph has boxicity at most two.^[7]

Block graphs are examples of pseudo-median graphs: for every three vertices, either there exists a unique vertex that belongs to shortest paths between all three vertices, or there exists a unique triangle whose edges lie on these three shortest paths.^[7]

The line graphs of trees are exactly the block graphs in which every cut vertex is incident to at most two blocks, or equivalently the claw-free block graphs. Line graphs of trees have been used to find graphs with a given number of edges and vertices in which the largest induced subgraph that is a tree is as small as possible.^[8]

The block graphs in which every block has size at most three are a special type of cactus graph, a triangular cactus. The largest triangular cactus in any graph may be found in polynomial time using an algorithm for the matroid parity problem. Since triangular cactus graphs are planar graphs, the largest triangular cactus can be used as an approximation to the largest planar subgraph, an important subproblem in planarization. As an approximation algorithm, this method has approximation ratio 4/9, the best known for the maximum planar subgraph problem.^[9]

If G is any undirected graph, the block graph of G, denoted B(G), is the intersection graph of the blocks of G: B(G) has a vertex for every biconnected component of G, and two vertices of B(G) are adjacent if the corresponding two blocks meet at an articulation vertex. If K₁ denotes the graph with one vertex, then B(K₁) is defined to be the empty graph. B(G) is necessarily a block graph: it has one biconnected component for each articulation vertex of G, and each biconnected component formed in this way must be a clique. Conversely, every block graph is the graph B(G) for some graph G.^[4] If G is a tree, then B(G) coincides with the line graph of G.

The graph B(B(G)) has one vertex for each articulation vertex of G; two vertices are adjacent in B(B(G)) if they belong to the same block in G.^[4]