Information Technology Reference
In-Depth Information
u
u
u
K
7
u
7
z
w
z
w
z
v
7
v
v
v
(a)
(b)
(c)
Fig. 7.
Illustration of the reduction used in Theorem 5. (a) An instance
G
of 1-planarity testing;
(b) The reduced instance
G
f
of fan-planarity testing. (c) Two adjacent edges of
G
that cross one
to another in
ʓ
; the crossing can be removed by rerouting the two edges as shown by the dashed
lines.
6 Open Problems
We suggest two questions: (
i
) What is the minimumnumber of edges of maximal fan-
planar graphs? (
ii
) Can we efficiently recognize maximally dense fan-planar graphs?
References
1. Ackerman, E.: On the maximumnumber of edges in topological graphs with no fourpairwise
crossing edges. Discrete & Computational Geometry 41(3), 365-375 (2009)
2. Ackerman, E., Fulek, R., Toth, C.D.: Graphs that admit polyline drawings with few crossing
angles. SIAM J. on Discrete Mathematics 26(1), 305-320 (2012)
3. Ackerman, E., Tardos, G.: On the maximumnumber of edges in quasi-planar graphs. J. of
Combinatorial Theory, Series A 114(3), 563-571 (2007)
4. Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear
number of edges. Combinatorica 17(1), 1-9 (1997)
5. Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line grid drawings of 3-connected
1-planar graphs. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 83-94.
Springer, Heidelberg (2013)
6. Angelini, P., Di Battista, G., Didimo, W., Frati, F., Hong, S.H., Kaufmann, M., Liotta, G., Lu-
biw, A.: Largeangle crossing drawingsofplanargraphs in subquadratic area. In: Marquez,
A., Ramos, P., Urrutia, J. (eds.) EGC 2011. LNCS, vol. 7579, pp. 200-209. Springer, Hei-
delberg (2012)
7. Asano, K.: The crossing number of
K
1
,
3
,n
and
K
2
,
3
,n
. J. of Graph Theory 10(1), 1-8 (1986)
8. Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reisl-
huber, J.: Recognizing outer 1-planar graphs in linear time. In: Wismath, S., Wolff, A. (eds.)
GD 2013. LNCS, vol. 8242, pp. 107-118. Springer, Heidelberg (2013)
9. Auer, C., Brandenburg, F.J., Gleißner, A., Hanauer, K.: On sparse maximal 2-planar graphs.
In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 555-556. Springer,
Heidelberg (2013)
10. Brandenburg, F.J., Eppstein, D., Gleißner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.:
On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012.
LNCS, vol. 7704, pp. 327-338. Springer, Heidelberg (2013)
11. Cheong,O.,Har-Peled, S., Kim, H., Kim, H.S.: On the number of edges of fan-crossing free
graphs. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol. 8283, pp.
163-173. Springer, Heidelberg (2013)
