  Inspired by the artwork of Mark Lombardi, we study the problem of
constructing orthogonal drawings where a small number of horizontal and
vertical line segments covers all vertices. We study two problems on orthogonal
drawings of planar graphs, one that minimizes the total number of line segments
and another that minimizes the number of line segments that cover all the
vertices. We show that the first problem can be solved by a non-trivial
modification of the flow-network orthogonal bend-minimization algorithm of
Tamassia, resulting in a polynomial-time algorithm. We show that the second
problem is NP-hard even for planar graphs with maximum degree 3. Given this
result, we then address this second optimization problem for trees and
series-parallel graphs with maximum degree 3. For both graph classes, we give
polynomial-time algorithms for upward orthogonal drawings with the minimum
number of segments covering the vertices.
