Packing and Covering Triangles in K 4-free Planar Graphs

We show that every K ₄-free planar graph with at most ν edge-disjoint triangles contains a set of at most ${\frac32\nu}$ edges whose removal makes the graph triangle-free. Moreover, equality is attained only when G is the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for any c?<?2 there are K ₄-free graphs with at most ν edge-disjoint triangles that need more than cν edges to cover all triangles.     

Common Tangents to Spheres in ℝ3

We prove that four spheres in ℝ³ have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent.     

Tilings of triangles

Let T be a non-equilateral triangle. We prove that the number of non-similar triangles Δ such that T can be dissected into triangles similar to Δ is at most 6. On the other hand, for infinitely many triangles T there are six non-similar triangles Δ such that T can be dissected into congruent triangles similar to Δ. For the equilateral triangle there are infinitely many such Δ. We also investigate the number of pieces in the dissections of the equilateral triangle into congruent triangles.     

A note on a conjecture of Gallai

A conjecture of Gallai states that if a graphG onn vertices contains no subgraph isomorphic to a wheel then the number of triangles inG is at mostn ²/8. In this note it is shown that this number is at most (1 +o(1))n ²/7, and in addition we exhibit a large family of graphs that shows that if the conjecture is true then there are many extremal examples.     

Realizability of Graphs

A graph is d-realizable if, for every configuration of its vertices in E^N, there exists a another corresponding configuration in E^d with the same edge lengths. A graph is 2-realizable if and only if it is a partial 2-tree, i.e., a subgraph of the 2-sum of triangles in the sense of graph theory. We show that a graph is 3-realizable if and only if it does not have K₅ or the 1-skeleton of the octahedron as a minor.     

Tilings of polygons with similar triangles

We prove that if a polygonP is decomposed into finitely many similar triangles then the tangents of the angles of these triangles are algebraic over the field generated by the coordinates of the vertices ofP. IfP is a rectangle then, apart from four sporadic cases, the triangles of the decomposition must be right triangles. Three of these sporadic triangles tile the square. In any other decomposition of the square into similar triangles, the decomposition consists of right triangles with an acute angle such that tan is a totally positive algebraic number. Most of the proofs are based on the following general theorem: if a convex polygonP is decomposed into finitely many triangles (not necessarily similar) then the coordinate system can be chosen in such a way that the coordinates of the vertices ofP belong to the field generated by the cotangents of the angles of the triangles in the decomposition.This work was completed while the author had a visiting position at the Mathematical Institute of the Hungarian Academy of Sciences.     

Triangle Contact Representations and Duality

A?contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A?primal?Cdual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal?Cdual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a corner of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.     

Lines meeting four tangents of a curve of order three in 3-space

Let C be a directly differentiable curve of order 3 in real projective 3-spaceP ³; cf. 3. It is known that there exist 4 tangents of C which are met by a line; cf. 3. The purpose of this paper is to show that, in fact, any 4 tangents of C are met by exactly 2 lines; cf. Theorem 3.3.     

Packing and Covering Triangles in Planar Graphs

Tuza conjectured that if a simple graph G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles in G. It has been shown that this conjecture is true for planar graphs and the bound is sharp. In this paper, we characterize the set of extremal planar graphs.     

Triangles in arrangements of lines

A set of n lines in the projective plane divides the plane into a certain number of polygonal cells. We show that if we insist that all of these cells be triangles, then there are at most $\text{1}\text{3}\text{n(n ? 1) + 4 ?}\text{2}\text{7}\text{n}$ of them. We also observe that if no point of the plane belongs to more than two of the lines and n is at least 4, some of the cells must be either quadrangles or pentagons. We further show that for $\text{n ≧ 4}$, there is a set of n lines which divides the plane into at least $\text{1}\text{3}\text{n(n ? 3) + 4}$ triangles.     

On Levels in Arrangements of Surfaces in Three Dimensions

A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n ??pseudo-planes?? or ??pseudo-spherical patches?? (where the main criterion is that each triple of surfaces has at most two common intersections), we prove that there are at most O(n ^2.997) vertices at any given level.     

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erd?s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.In the plane, our main result is an O(n44/19)=O(n^2.3158) upper bound on the number of unit-area triangles spanned by n points, which is the first breakthrough improving the classical bound of O(n7/3) from 1992. We also make progress in a number of important special cases. We show that: (i) For points in convex position, there exist n-element point sets that span Ω(nlogn) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most ; there exist n-element point sets (for arbitrarily large n) that span (6/π²−o(1))n² minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span Ω(nlogn) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds).In 3-space we prove an O(n17/7β(n))=O(n^2.4286) upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, O(n8/3), is an old result of Erd?s and Purdy from 1971. We further show, for point sets in 3-space: (i) The number of minimum nonzero area triangles is at most n²+O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span Ω(n4/3) triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is O(n4/3+ε), for any ε>0. (iii) Every set of n points, not all on a line, determines at least Ω(n2/3/β(n)) triangles of distinct areas, which share a common side.     

Two circles and their common tangents

Given two circles C ₁ and C ₂ in a plane such that neither one of the two circles is contained in the other, there are either four common tangents when the circles do not intersect at all or the circles have three common tangents when they touch each other externally or only two common tangents when the circles intersect exactly at two points. The article oulines analytical procedures for computing the equations of these common tangents. Using the built-in Maple of the software Scientific Work Place 3.0, the diagrams of the circles with their common tangents are incorporated in this article.     

and Norms Error Estimates in Finite Element Method for Linear Parabolic Interface Problems

We derive new a priori error estimates for linear parabolic equations with discontinuous coefficients. Due to low global regularity of the solutions the error analysis of the standard finite element method for parabolic problems is difficult to adopt for parabolic interface problems. A finite element procedure is, therefore, proposed and analyzed in this paper. We are able to show that the standard energy technique of finite element method for non-interface parabolic problems can be extended to parabolic interface problems if we allow interface triangles to be curved triangles. Optimal pointwise-in-time error estimates in the L ²(Ω) and H ¹(Ω) norms are shown to hold for the semidiscrete scheme. A fully discrete scheme based on backward Euler method is analyzed and pointwise-in-time error estimates are derived. The interfaces are assumed to be arbitrary shape but smooth for our purpose.     

Hot spots conjecture for a class of acute triangles

We show that the hot spots conjecture of J. Rauch holds for acute triangles if one of the angles is not larger than \(\pi /6\). More precisely, we show that the second Neumann eigenfunction on those acute triangles has no maximum or minimum inside the domain. We first simplify the problem by showing that absence of critical points on two sides implies no critical points inside a triangle. This result applies to any acute triangle and might help prove the conjecture for arbitrary acute triangles. Then we show that there are no critical points on two sides assuming one small angle. We also establish simplicity for the smallest positive Neumann eigenvalue for all non-equilateral acute triangles. This result was already known for obtuse triangles, and it fails for the equilateral case.     

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K ₄-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.     

Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

Congruence criteria for finite subsets of complex projective and complex hyperbolic spaces

We investigate congruence classes and direct congruence classes of m-tuples in the complex projective space ℂP ⁿ . For direct congruence one allows only isometries which are induced by linear (instead of semilinear) mappings. We establish a canonical bijection between the set of direct congruence classes of m-tuples of points in ℂP ⁿ and the set of equivalence classes of positive semidefinite Hermitean m×m-matrices of rank at most n+1 with 1's on the diagonal. As a corollary we get that the direct congruence class of an m-tuple is uniquely determined by the direct congruence classes of all of its triangles, provided that no pair of points of the m-tuple has distance π/2. Examples show that the situation changes drastically if one replaces direct congruence classes by congruence classes or if distances π/2 are allowed. Finally we do the same kind of investigation also for the complex hyperbolic space ℂH ⁿ . Most of the results are completely analogous, however, there are also some interesting differences. Received: 15 January 1996