**Square-contact representations of partial 2-trees and triconnected simply-nested graphs**.

G. Da Lozza, W. E. Devanny, D. Eppstein, and T. Johnson.

arXiv:1710.00426.

*Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017)*, Phuket, Thailand, 2017.

Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.

We show that the

*K*_{1,1,3}-free partial 2-trees and the Halin graphs other than*K*_{4}can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.**Quadratic time algorithms appear to be optimal for sorting evolving data**.

J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.

*Proc. Algorithm Engineering & Experiments (ALENEX 2018)*, New Orleans, 2018, to appear.

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.