Top

previous chapter Peacock Bundles: Bundle Coloring for Graphs wit...

next chapter Multi-colored Spanning Graphs

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Twins in Subdivision Drawings of Hypergraphs

Read first chapter

Authors: René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

Visualizing hypergraphs, systems of subsets of some universe, has continuously attracted research interest in the last decades. We study a natural kind of hypergraph visualization called subdivision drawings. Dinkla et al. [Comput. Graph. Forum ’12] claimed that only few hypergraphs have a subdivision drawing. However, this statement seems to be based on the assumption (also used in previous work) that the input hypergraph does not contain twins, pairs of vertices which are in precisely the same hyperedges (subsets of the universe). We show that such vertices may be necessary for a hypergraph to admit a subdivision drawing. As a counterpart, we show that the number of such “necessary twins” is upper-bounded by a function of the number m of hyperedges and a further parameter r of the desired drawing related to its number of layers. This leads to a linear-time algorithm for determining such subdivision drawings if m and r are constant; in other words, the problem is linear-time fixed-parameter tractable with respect to the parameters m and r.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

We refer to Kaufmann et al. [ 15] for a method to obtain a subdivision drawing from a planar support.

Results labeled by \(\star \) are deferred to a full version of the paper.

Each planar graph has an ordering of the vertices such that each vertex has at most five neighbors later in the ordering. To achieve \(n^{{\text {O}}(n)}\) enumeration time we simply guess such an ordering and then for each vertex its at most five later neighbors.

Alsallakh, B., Micallef, L., Aigner, W., Hauser, H., Miksch, S., Rodgers, P.J.: The state-of-the-art of set visualization. Comput. Graph. Forum 35(1), 234–260 (2016) CrossRef

Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30(3), 479–513 (1983) MathSciNetCrossRefMATH

Bixby, R.E., Wagner, D.K.: An almost linear-time algorithm for graph realization. Math. Oper. Res. 13(1), 99–123 (1988) MathSciNetCrossRefMATH

Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Blocks of hypergraphs—applied to hypergraphs and outerplanarity. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 201–211. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-19222-7_21 CrossRef

Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Path-based supports for hypergraphs. J. Discrete Algorithms 14, 248–261 (2012) MathSciNetCrossRefMATH

Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533–549 (2011) MathSciNetCrossRefMATH

Chen, J., Komusiewicz, C., Niedermeier, R., Sorge, M., Suchý, O., Weller, M.: Polynomial-time data reduction for the subset interconnection design problem. SIAM J. Discrete Math. 29(1), 1–25 (2015) MathSciNetCrossRefMATH

Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015) CrossRefMATH

Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2010) CrossRefMATH

10.

Dinkla, K., van Kreveld, M.J., Speckmann, B., Westenberg, M.A.: Kelp diagrams: point set membership visualization. Comput. Graph. Forum 31(3), 875–884 (2012) CrossRef

11.

Eschbach, T., Günther, W., Becker, B.: Orthogonal hypergraph drawing for improved visibility. J. Graph Algorithms Appl. 10(2), 141–157 (2006) MathSciNetCrossRefMATH

12.

Flower, J., Fish, A., Howse, J.: Euler diagram generation. J. Vis. Lang. Comput. 19(6), 675–694 (2008) CrossRef

13.

Habib, M., Paul, C., Viennot, L.: Partition refinement techniques: an interesting algorithmic tool kit. Int. J. Found. Comput. Sci. 10(2), 147–170 (1999) MathSciNetCrossRefMATH

14.

Johnson, D.S., Pollak, H.O.: Hypergraph planarity and the complexity of drawing Venn diagrams. J. Graph Theory 11(3), 309–325 (1987) MathSciNetCrossRefMATH

15.

Kaufmann, M., Kreveld, M., Speckmann, B.: Subdivision drawings of hypergraphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 396–407. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-00219-9_39 CrossRef

16.

Klemz, B., Mchedlidze, T., Nöllenburg, M.: Minimum tree supports for hypergraphs and low-concurrency Euler diagrams. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 265–276. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-08404-6_23 CrossRef

17.

Korach, E., Stern, M.: The clustering matroid and the optimal clustering tree. Math. Program. 98(1–3), 385–414 (2003) MathSciNetCrossRefMATH

18.

Mäkinen, E.: How to draw a hypergraph. Int. J. Comput. Math. 34, 178–185 (1990) CrossRefMATH

19.

Tarjan, R., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566–579 (1984) MathSciNetCrossRefMATH

20.

Tutte, W.T.: How to draw a graph. Proc. London Math. Soc. 13(3), 743–768 (1963) MathSciNetCrossRefMATH

21.

Verroust, A., Viaud, M.-L.: Ensuring the drawability of extended Euler diagrams for up to 8 sets. In: Blackwell, A.F., Marriott, K., Shimojima, A. (eds.) Diagrams 2004. LNCS (LNAI), vol. 2980, pp. 128–141. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-25931-2_13 CrossRef

Title

Twins in Subdivision Drawings of Hypergraphs

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_6

Authors:

René van Bevern
Iyad Kanj
Christian Komusiewicz
Rolf Niedermeier
Manuel Sorge

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits