## Abstract

We define the visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw two collinear edges of the same vertex). Let n denote the number of vertices of a graph. We show that trees can be drawn with 3n / 4 straight-line segments on a polynomial grid, and with n / 2 straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with (8n−17)/3

(8n−17)/3

segments on an O(n)×O(n 2 )

O(n)×O(n2)

grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n / 2 edges on an O(n)×O(n 2 )

O(n)×O(n2)

grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3

(5n−11)/3

arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.

(8n−17)/3

segments on an O(n)×O(n 2 )

O(n)×O(n2)

grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n / 2 edges on an O(n)×O(n 2 )

O(n)×O(n2)

grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3

(5n−11)/3

arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.

Original language | English |
---|---|

Title of host publication | 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG) |

Subtitle of host publication | Revised Selected Papers |

Editors | Gerhard J. Woeginger, Hans L. Bodlaender |

Publisher | Springer |

Pages | 316-329 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-319-68705-6 |

ISBN (Print) | 978-3-319-68704-9 |

DOIs | |

Publication status | Published - 2017 |

Event | 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017) - Kapellerput, Eindhoven, Netherlands Duration: 21 Jul 2017 → 23 Jul 2017 http://www.win.tue.nl/wg2017/ |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10520 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017) |
---|---|

Abbreviated title | WG 2017 |

Country | Netherlands |

City | Eindhoven |

Period | 21/07/17 → 23/07/17 |

Internet address |