On the bend-number of planar and outerplanar graphs

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book , Preprint , Conference object 01 Jan 2012Embargo end date: 01 Jan 2011 France English Publisher:Elsevier BVJournal:Discrete Applied Mathematics, volume 179, pages 109-119 (issn: 0166-218X,

Copyright policy )Funded by:DFG | unidentified

Authors: Heldt, Daniel; Knauer, Kolja; Ueckerdt, Torsten;

doi: 10.1016/j.dam.2014.07.015 , 10.1007/978-3-642-29344-3_39 , 10.48550/arxiv.1112.3353

arXiv: 1112.3353

On the bend-number of planar and outerplanar graphs

- Summary
- Subjects
- Metrics

Abstract

The bend-number b(G) of a graph G is the minimum k such that G may be represented as the edge intersection graph of a set of grid paths with at most k bends. We confirm a conjecture of Biedl and Stern showing that the maximum bend-number of outerplanar graphs is 2. Moreover we improve the formerly known lower and upper bound for the maximum bend-number of planar graphs from 2 and 5 to 3 and 4, respectively.

appears in proceedings of 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)

Country

France

Related Organizations

View all View all

Keywords

FOS: Computer and information sciences, Discrete Mathematics (cs.DM), G.2.1; F.2.2, Graph representations (geometric and intersection representations, etc.), planar graph, G.2.1, [INFO] Computer Science [cs], Planar graphs; geometric and topological aspects of graph theory, EPG-representation, outerplanar graph, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C62, F.2.2, bend-number, Computer Science - Discrete Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	19
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%