The crisis revealed several weaknesses in the Basel II system: little consideration of the risk of liquidity, the procyclical nature of banks, the failure of internal controls to function, etc.

2 The member States of the European Union are required (by Directive 94/19/EC) to set up a system to guarantee deposits that ensures, in a short time, a payment to depositors that is calculated according to a minimum harmonized level of 20,000 euros. Following the crisis, the European Union raised the minimum level of the guarantee to 50,000 euros beginning on June 30, 2009 and harmonization at a level of 100,000 euros beginning on December 31, 2011.

3 The crisis showed clearly the insufficiency of supervision. Reforms of existing systems were undertaken at the national and European levels. The European System of Financial Supervisors coordinates a network of national supervisors with European institutions for controlling banks, insurance, and stock exchanges.

In the summer of 2007, the financial systems of European countries were hit full force by a crisis of great magnitude. They were, by their behavior, the protagonists of this crisis and the first surviving victims of the central banks and States. Certain financial systems stood up to the crisis better than others, but all experienced dysfunctions that clearly showed the limits of the forms of governance and the forms of public intervention that characterized them. The banking system and the financial markets are both components of a financial system; the former is subject to European control and regulation, while the latter are free because they are supposed to regulate themselves.

Public intervention in the banking sector takes three main forms: prudential regulation, especially with the Basel II ratio for adequacy of a bank's own funds for their exposure to risk 1 ; insuring deposits, the goal of which is to ensure a minimum level of protection for depositors and savers in order to avoid a run on banks 2 ; and control and supervision of banks by public authorities, which ensures that the rules are applied properly. 3 Intervention by central banks, through their monetary policy and as lenders of last resort, constitutes the fourth means of regulating the banking system, and the main form of intervention in financial markets. Central banks intervene in order to ensure the stability of financial systems. The financial crisis has shown that traditional modes of public intervention in the financial system are ineffective and insufficient. Before analyzing the principles and limits of these forms of public intervention, we are going to examine cases of exceptional intervention and support to banks by public powers during the crisis. Then, in conclusion, we will compare these forms of public intervention with the current state of financial systems.

For an exceptional financial crisis, exceptional public intervention

At the start of this crisis, called the crisis of "subprimes," at the beginning of 2007, was a fall in the market value of securities backed by American subprime mortgage loans, real estate loans made to borrowers with little solvency who were excluded from the credit market. This fall followed the realization of the lack of solvency of subprime lenders, including the American company New Century Financial, which declared bankruptcy on April 2, 2007. Banks that held these securities in their assets would then become aware of the illiquidity of these securities. They would declare their losses and raise their conditions for doubtful debt on the American real estate market. In June 2007, the fifth largest American investment bank, Bear Stearns, bailed out two of its hedge funds that were exposed to American subprime loans. It was followed in August 2007 by BNP Paribas, which announced the suspension of trading of three of its investment funds that were exposed to subprime loans, and by the German bank IKB Deutsche Industriebank AG, which, holding securities backed by subprime loans called "toxic" securities, was saved from bankruptcy by its mother house, the public bank KfW. The end of 2007 would be characterized by a succession of announcements of losses produced by depreciations of toxic securities. 4 On September 13, 2007, Northern Rock, the fifth largest British real estate lender, asked the Bank of England for an emergency loan; on October 24, Merrill Lynch announced major losses, and would be followed by UBS and Citigroup banks. These different events led to great tension and a loss of confidence on the part of the markets, especially money markets. European banks faced problems with financing, a contraction of interbank loans, and a rise in the rates for interbank borrowing. Faced with the deterioration of their balance sheets, banks sought to get out of debt and to ration the credit they offered. Over the course of 2008, most banks saw their situation worsen, and systemic risk reached its height in September. On September 7, the American Treasury took control of the mortgage credit agencies Freddie Mac and Fannie Mae; on September 15, Lehman Brothers, the fourth largest American investment bank, went bankrupt, and Bank of America announced that it was buying Merrill Lynch; on September 16, the world's largest insurance company AIG was nationalized by the Fed and the American government. Starting in October 2008, the world financial crisis entered a second phase. It grew worse; the danger of a systemic crisis became greater, and the world's large economies 4 According to an IMF study, losses and depreciation of assets of French banks make up 3% of the world total counted in mid-2009. According to Bloomberg data, among the top 25 with the greatest losses and depreciations are 11 American banks, with at the top of the list Citigroup, Wachovia, Bank of America, and JP Morgan, for a total of $600 billion; 4 British banks with a total of $166 billion; 2 Swiss banks, 3 German banks, 2 Dutch banks, 1 Spanish bank, and 2 French banks (Société générale and BNP Paribas) with a total of $39 billion in losses. saw a recession for more than two years. Beginning in the summer of 2010, the financial crisis, which caused a swelling of debt and public deficits, was transformed into a sovereign debt crisis. Before the crisis, the situation of public finances in the countries of the euro zone was globally satisfactory; with the crisis, public deficits grew (Mathieu and Sterdyniak, 2011). Budget imbalances grew worse because of, on one hand, injections of public funds into the financial sector, and on the other hand, the fall in revenue caused by the economic recession (see the chapter by Philippe Bance below). The financial markets then decided that this deterioration of public debt increased the risk of insolvency for States. They revised sharply upward the risk premiums on the sovereign debt of several European states, especially those on Ireland, Greece, Portugal, Spain, and Italy. There followed the establishment of restrictive policies, a sharp reduction of public spending, and strengthening of the supervision of budgetary policies, accompanied by the establishment of a temporary financial aid system for member States that were having trouble getting access to financing on the markets. The behavior of the markets turned against banks, their main actors. Banks that held sovereign debt had to face a devaluation of their assets and an increased risk of losses. According to the European Central Bank (ECB), this risk must be relativized. In the case of French banks, for example, their exposure to sovereign debt of the countries of southern Europe makes up 38% of their own funds (Tier 1), and they hold 8% of the Greek sovereign debt.

Beginning in August 2007 and throughout 2008, central banks and States intervened massively to save financial systems. Banks, facing a high risk of insolvency, had to increase their solvency ratio, either by reducing their assets, especially outstanding bills for credit given, or by increasing their own funds by recapitalization. Moreover, they also had to continue refinancing themselves in order to meet their commitments. The general context of uncertainty and distrust led to a crisis of liquidity, which required refinancing of banks and led to a restriction of credit. It also contributed to a sharp fall of financial markets, which led to a rise in the cost of recapitalizing banks on the stock market. Facing the risk of financial systems freezing and the financial crisis turning into an economic crisis, public powers decided to support financial systems. In Europe, this support occurred in two stages, reserved support until September 2008, then solid and committed support by the ECB and certain States, which did not prevent a severe economic recession.

At the beginning of the crisis, central banks tried to contain it by injecting exceptional liquidity into the interbank market in order to restore a climate of confidence among banks. When this initiative proved to be insufficient, the Fed quickly adopted measures of "conventional" monetary policy that consisted of lowering its intervention rates. The ECB adopted these measures in October 2008, lowering its intervention rate from 4.25% to 1%, which led to the lowering of reference rates on the interbank market (Figure 1). At the end of 2008, central banks faced a market crisis; they then put in place "unconventional" measures that consisted of meeting all of banks' needs for liquidity, providing liquidity in cash, extending the duration of refinancing operations, enlarging the list of eligible assets, but also buying secured bonds and government bonds. 5 The goal pursued by central banks was to increase massively the amount of money in the economy and reinvigorate the markets by buying securities directly and substituting themselves for banks to finance the economy (Loisel and Mésonnier, 2009).

The primary mission of the ECB is the stability of the prices of goods and services (ECB, 2011). To ensure the success of this mission, it sets its intervention rate and, by open market operations, stabilizes the daily interbank rate (EONIA) at a level close to this intervention rate. 6 In a normal economic situation, refinancing operations and required reserves are the two pillars of the monetary policy of the ECB, which, by combining them, stabilizes the interbank rate very close to the intervention rate. 6 To carry out its monetary policy, the ECB uses six tools: short-term refinancing operations (Main Refinancing Operations, or MROs), required reserves, longer term refinancing operations (LTROs), fine tuning operations, permanent facilities (every day, banks can borrow from or lend to the central bank an unlimited amount at a rate +/-1% of the intervention rate for 24 hours), and collateral (each time a bank refinances itself with the ECB, it must mobilize assets that will serve as collateral).

7 The ECB offers banks variable rate loans for seven days. The minimum rate for the loan is the intervention rate. The ECB sets the total amount loaned, the benchmark, according to the amount of liquidity it deems necessary for the economy, so that banks can meet their obligations for reserves. Credit establishments of the euro zone are compelled to form required reserves (the current reserve rate is 2% of deposits) for accounts opened with national central banks. The reserves are formed for a period of four weeks and are paid.

Between August 2007 and September 2008, the ECB's policy consisted of injecting liquidity daily according to the demand in the banking sector while maintaining the total amount of liquidity at a globally constant level. This policy increased the cost of liquidity, since banks were refinancing themselves at rates that were on average above the intervention rate. Since the ECB's main goal was to control inflationary tendencies, it did not lower its intervention rate during the first year of the crisis. The results of its behavior were greater volatility of the daily interbank rate, the EONIA, and a rise in three month interbank rates, the EURIBOR 3 months, reflecting a high level of distrust on the interbank markets (Figure 1). With the aggravation of the crisis beginning in September 2008, the ECB changed its policy radically. It participated in the concerted lowering of rates (minus 50 base points) carried out jointly by the Fed, the Bank of Canada, the Bank of England, the Bank of Sweden, and the Swiss National Bank, and it lowered its rates 325 base points in seven months (to 1% in May 2009). It gave banks the possibility of borrowing at any maturity at a fixed rate (the intervention rate), and in currency other than the euro, the liquidity they needed (the benchmark or maximum amount that the ECB is willing to loan was temporarily eliminated and replaced by full allotment). In these conditions, banks preferred borrowing liquidity from the ECB rather than depending on other banks of whose solvency they were uncertain. The excess liquidity drew down interbank rates, which stayed close to or lower than intervention rates until April 2011 (the intervention rate went to 1.25%). In May 2010, the financial crisis entered a third phase, becoming a crisis of sovereign debt. The ECB maintained its "unconventional" operations in order to reduce the effects of the crisis on the markets.

Intervention by States took different forms depending on countries (see the chapter by Luc Bernier below). It was essentially aid for refinancing in the form of guarantees and lines of credit, aid for capitalization, and aid for undoing assets (Plane and Pujals, 2009). Between September 2008 and February 2009, close to 40% of increases in the capital of euro zone banks was due to injections of capital by public powers. In France, the government created the State Company for Public Participation (SPPE) to allow the recapitalization of banks to a ceiling of 40 billion euros.

On October 10, 2008, the heads of State and of government of the G7 oriented the action of States around three axes: suspension of the application of international accounting norms (questioning the principle of valuation by the market price, Fair Value); recapitalization of banks, even State participation in the capital of banks; and a commitment not to let any bank "of systemic importance" go bankrupt, to provide a public guarantee of interbank loans and re-regulation. 8 At the European level, member States gave themselves three mechanisms that were supposed to guarantee European financial stability (Noyer, 2011). In May 2010, they created, for a period of three years, a European Financial Stability Facility (EFSF). In March 2011, the size of the fund was raised to an effective amount of 400 billion euros. They also approved the establishment beginning in 2013 of a European Stability Mechanism (ESM) provided with a loan capacity of 500 billion euros that would make possible exceptional intervention on the primary markets for sovereign debt. Finally, beginning in July 2013, there will be not issuing of eurobonds but integration of normalized and identical collective action clauses (CACs) into all contracts for issuing of government bonds in the euro zone for longer than one year of collective action. How were these different forms of public intervention received by the financial systems? Did they reach their goal of reassuring the markets? In view of the panic that hit the financial markets again in the summer of 2011, it seems that the goal was not reached.

Between the summer of 2007 and the beginning of 2009, the stock markets collapsed, before starting to move upward again, showing a certain level of confidence in the measures taken by the central banks and States. In May 2011, the stock markets of Germany, the United Kingdom, and the United States regained their 2006 levels, while those of Ireland, Greece, Portugal, and Italy had lost more than 50% (Figures 2 and3). The financial and economic crisis was deepened by the increase in the correlation between the banking sector and the economy as a whole, which had the important result of spreading the financial crisis to the economy as a whole. At the European level, the correlation between yields of the economy as a whole and those of the banking sector rose to 0.95 in May 2007, before the onset of the crisis, and with a correlation of 0.92 in May 2011, it has remained at a high level, which continues to cause risk for the European economy. The development of the correlation between the banking sector and the economy as a whole varies depending on the European country. On one hand, countries like Greece, Portugal, and Spain saw a strong increase in the correlation between their banking sectors and their economies as a whole, making them more vulnerable when facing a breakdown of this sector. On the other hand, the other European countries saw their correlation either maintain the same level as before the crisis, which is especially the case for France, or decline, which was the case for Italy, Ireland, the Netherlands, Belgium, and Germany. 9 Some people might think that these countries would be less affected in case of new breakdowns in their banking system, but this would be to forget too quickly the strong dependence among European banking systems. This dependence was notably favored by the establishment of a common system of regulation, which rather than preventing crises, contributes to their appearance by pushing banks to behave the same way toward risk. 9 The correlation was calculated between the indices representing the stock markets and those for the banking sector in each country and for the euro zone, for two periods: January 2006-March 2007 and April 2007-May 2011.

The financial crisis: the result of outdated traditional means of public intervention

Aware of the central role played by banking systems in economies, public authorities subject them to regulations and controls. By their transforming activity, banks have structural fragility: they are exposed to the risk of illiquidity of their loans while facing liquid deposits. A first means of public intervention seeks to limit this transformation ahead of time. This is the international prudential regulations decreed by the Basel Committee, which require banks to hold enough capital in proportion to the risks they take. The Basel II prudential ratio in effect since 2007 requires banks to have their own funds making up at least 8% of the total of three weighted risks (credit, market, and operational). The goal announced by the Committee when this ratio was created was to push banks to set up performing models to measure risks and to improve their internal control systems. This goal has not been reached: on the contrary, the Basel II system bears part of the responsibility for the crisis, for at least four reasons.

While the transforming activity of banks' financial commitments naturally exposes them to risks concerning liquidity, these risks are not taken into account in the prudential ratio. The present crisis began by a crisis of liquidity, which then exacerbated credit, market, and operational risks. Banks owe it to themselves to respect a simple short-term liquidity ratio that guarantees that liquid assets for a month must at least cover liabilities due for a month. This ratio is calculated on the basis of assets and liabilities on the balance sheet; it does not include the possibility that in a context of uncertainty and tension on the markets, assets can quickly become illiquid, thus increasing banks' exposure to risks to liquidity.

The establishment of the Basel II solvency ratios was accompanied by new accounting rules that applied to businesses and banks listed on the markets and imposed on them the principle of valuation of their balance sheet at market value (Fair Value). The combination of this principle, which serves as a reference for calculating solvency ratios, and new prudential rules favored procyclical behavior by banks. In periods of market euphoria, the more the value of assets increases, the more banks will lend and take risks; on the other hand, when markets go down, the value of assets collapses, banks reduce their activity and increase their own funds.

It is true that the Basel II system was implemented only shortly before the crisis, but banks, especially European banks, had anticipated the move from the Basel I ratio to the Basel II ratio. They quickly developed very complex "advanced" models that calculate the three great risks independently of each other but above all allowed them to follow weaker requirements for their own funds. Banks saw prudential regulation not as a way of regulation encouraging them to know better their exposure to risks in order to limit potential losses but as a constraint that, by forcing them to immobilize part of their own funds, harmed their profitability. They then resorted to financial innovations in order to "take out" of their balance sheets risky assets and transfer them to investors who were only slightly subject (like insurers) or not subject at all (shadow banking) to prudential regulation. During the period of market euphoria, banks had "forgotten" the low-quality assets that they had transferred to other establishments. With the crisis, they were faced with a massive return of assets to degrade on their balance sheets.

Finally, the crisis has shown the deficiencies of internal control or self-control of risk by banks, which is one of the pillars of Basel II. Within banks, the establishment of a culture of risk control, an internal organization separating operational activities and activities to control these same activities, and models for quantification and evaluation of risk based in large majority on Value at Risk, VaR, did not prevent either excessive risk-taking by some banks or the danger of a systemic crisis. The Basel II Committee and the supervisory authorities delegated to banks their control functions without giving themselves sufficient means to evaluate the tools and procedures for risk management established by each bank. They overestimated banks' ability to establish effective internal controls. The crisis clearly showed the insufficiencies of prudential regulation, but it also revealed the failures and limits of supervision, which is to say, of the national public institutions responsible for ensuring that financial establishments comply with the rules defined by regulators. Before the crisis, each country had several supervisory authorities without there existing, within each country but also between countries, any coordination between different authorities. Following the crisis, it seems obvious that supervision must be macroprudential, and European if not international (Dabrowski, 2010).

It has also shown the limits of the deposit insurance schemes chosen by national public powers to protect not only national depositors but also those who live in other countries. In the European Union, countries must meet a common directive, the Deposit Guarantee Schemes Directive (DGD), which defines the fundamental principles of deposit insurance but allows States a certain autonomy in choosing their scheme. From this results a diversity of schemes in terms of types of deposits covered, ways of joining, calculating rates, the amount covered, settling bankruptcies, and the status of the deposit insurer, which is especially favorable for the development of moral risk and opting out (Eisenbeis and Kaufman, 2008). Joining the deposit insurance scheme should be mandatory for all financial establishments that have deposits of parties needing protection, such as individuals and small businesses, to limit opting out. When joining is voluntary, a bank that takes extraordinary risks will join the deposit insurance, thus guaranteeing for itself the insurer's support in case of difficulties, while a low-risk bank will not. The problem of moral risk arises when beneficiaries of protection take exaggerated risks because they are protected, or think they are, against losses, or believe that the authorities will intervene to prevent any bank failure.

Central banks, the last mechanism for public intervention, have also shown some failings in the crisis. They use intervention rates, the very short-term interest rates that they offer banks to refinance themselves, to reach their goal of stability of prices and to influence conditions of the credit supply. They are the lenders of last resort; they provide liquidity to banks that are at risk of default because they are unable to finance themselves on the interbank market or because they are insolvent but too big to fail. They support a failing bank in order to keep its failure from spreading to the entire system and producing a systemic crisis. The guarantee of automatic support from central banks can encourage moral risk in the financial system, since it favors banks taking high risks when granting credit or taking a position on the markets (Cukierman, 2011).

Central banks must favor targeted injections of liquidity to limit the use of liquidity for simple goals of speculation (Ewerhart and Valla, 2008). Regulating liquidity would be one way among others to reduce the pressure put on central banks in favor of liquidity injections in periods of crisis (Rochet, 2008).

After the financial crisis: better regulated European financial systems?

The Basel Committee, mandated by the governments of the G20 to draw the lessons of the crisis, defined a new prudential framework that should be respected by credit institutions in 2019 at the latest and that introduces, in addition to the Basel II solvency ratio, a "leverage" ratio, two liquidity ratios, and resistance tests.10 Banks should strengthen the character of their own funds in order to cover all risks and control the leverage effect. 11 The second pillar of Basel II already requires banks to supervise their indebtedness by the "leverage ratio" that measures the size of banks' commitments in relation to the size of their balance sheets. With Basel III, this ratio should be integrated into Pillar 1, and should therefore be integrated into the calculation of requirements for their own funds. In 2015 at best, if pressure by the banking lobby does not succeed in preventing the imposition of new ratios, banks will have to respect two ratios of liquidity, one for the short term (one month), the Liquidity Coverage Ratio (LCR), the other for the long term (one year), the Net Stable Funding Ratio (NSFR), to limit their exposure to liquidity risks. 12 The short-term liquidity ratio already exists; what is new is the application of the coefficient for weighting to assets and liabilities according to their degree of liquidity. Assets are all the more liquid as their issuers are solvent. To calculate the liquidity risk, banks will therefore have to evaluate the solvency of their issuers, either by using internal rating tools or by using external ratings by private rating agencies as references.

The committee persists in giving a central role to rating agencies in the evaluation of borrowers' solvency, when the agencies did not anticipate the losses by banks. They only modified their ratings after banks and States announced their difficulties. By their behavior, private rating agencies encourage panic on financial markets. While the crisis showed clearly the weaknesses of means of public intervention in financial systems, the public authorities were more than prudent in their reforms. Will the modifications made to Basel II make it possible to avoid other crises? The answer seems obvious. Before the liquidity crisis of 2007, banks were already following the "leverage" and short-term liquidity ratios, which did not prevent them from becoming overexposed to risk; they met the solvency ratios of Basel II, but clearly either they underestimated their risks or their risk evaluation models were incorrect, or their levels of their own funds were insufficient for a situation of systemic risk. The new prudential rules, like the old ones, will apply only to banks; what about regulation of activities of other actors in financial systems, such as institutional investors, who bear part of the responsibility for the crisis? Nothing, or not much. What about regulation of financial markets, especially Over The Counter markets where complex and opaque products with high risk are negotiated? Nothing. Banks can therefore innovate, take risks again, and transfer them, especially to localized entities in countries other than their country of origin. High concentration of banking is a source of instability, not only because it is a high risk factor in financing banks, but also because it increases the degree of dependence of an economy on a limited number of banking and financial groups, and the principle of "too big to fail" is strengthened.

The Spanish, French, and Dutch banking sectors quickly recovered their place in their countries' economies, while others, such as those of Belgium, Germany, Italy, Greece, and Portugal, saw decreases in their respective weight. In May 2011, Banco Santander and ING Groupe were among the most liquid values of the Spanish and Dutch economies, while banks like Commerzbank, KBC Groupe, and National Bank of Greece did not manage to recover their position from before the crisis (represented here by the reference stock index of each of the countries, Table 1). of banks in the management of the common good that money constitutes, is willing to support them financially without forcing them in exchange to limit activities that are too risky and may put the existence of this common good in danger. The financial markets react favorably to State financial support for the banking system, even if it leads to an increase in public deficits. On the other hand, they demand higher remuneration for government securities of States that have large public debts. Today, market discipline has become the reference; to be able to finance themselves on the markets, States must reduce their public debts, which involves their disengagement from social and industrial systems (see especially the chapters by Cathy Zadra-Veil, Hugues Jennequin, and David Flacher).

  7

Figure 1 :

 1 Figure 1: Interest rates in the Euro area, 2006-2011

Figure 2 :

 2 Figure 2: Evolution of indices shares from January 2006 to may 2011

Figure 3 :

 3 Figure 3: Evolution of indices shares from January 2006 to may 2011

Figure 4 :

 4 Figure 4: Evolution of indices of the banking sector from January 2006 to may 2011

Figure 5 :

 5 Figure 5: Evolution of indices of the banking sector from January 2006 to may 2011

Figure 7 :

 7 Figure 7: Changes in Weight and Position of European Banks on European Stock Markets (stock index: EURO STOXXX 50 PRICE EUR)

Figure 8 :

 8 Figure 8: Changes in Weight and Position of European Banks in the European Banking Sector (stock index: EUROSTOXX BANK PRICE EUR)

Table 1 :

 1 Changes in Weight of European Banks on the Stock Markets of their Countries (weight as % of the reference shares index)

	Countries	Banks	30Au 30.12.2005	Au 30.12.2008

On October 20, 2010, the European Commission presented its European outline project for the management of crises in the financial system.

The reader can consult http://www.bis.org/bcbs/basel3/b3summarytable.pdf for a synthesis of the Basel III prudential reforms.

The new norm anticipates an improvement in the quality of the "hard core" or Tier 1 of banks' own funds (capital provided by shareholders, increased by profits held in reserve), which will go from 2% to 4.5% with a "countercyclical" cushion of 2.5%. Tier 1 should therefore make up a minimum of 4.5% of weighted risks of banks and, in times of strong economic growth, it will be a maximum of 7% of weighted risks.

The goal of this ratio (outstanding one-year stable assets must be at least equal to outstanding one-year stable liabilities) is to force banks to hold assets of one year maturity that are easily negotiable in order to withstand thirty days of crisis.

Public powers quickly revised downward their requirements for regulation of financial systems under pressure from the banking lobby, but also because of banks' rapid return to profitability. In 2010, the earnings of the twelve largest European banks grew by 8.6%, and their Tier 1 solvency ratios were between 8.5% and 15.3% (Noyer, 2011). 2010 was marked by a return to profitability of European banks, including those in the European countries most affected by the economic crisis. Between 2008 and 2010, the profits of the two largest French banks increased, by more than 160% for BNP Paribas and more than 50% for Société Générale (Figure 6). European banks remain flagship values on the stock markets of the euro zone. After the crisis, 9 European banks appear among the 50 most liquid European values by the European stock index EURO STOXX 50 PRICE EUR (Figure 7). Despite the crisis, the supremacy of some banks remains unquestioned, and this in spite of the fact that their countries of origin are still affected by the economic crisis. The Spanish bank Banco Santander has maintained its third place on the European stock index and seen its weight increase after the crisis. Since October 2008, more and more coordinated and global public intervention has constituted a systemic change, since it replaced provisionally the State and central banks at the heart of the financial system. The only positive effect of the crisis has been to remind everyone that the State is the guarantor of the financial system's continuity. Without the intervention of the State, the stability of the financial system is threatened. The crisis has also served as a reminder that the relationship between the State and the financial system is biased: the financial system wants and expects the State to intervene when it is going through a crisis, but it does not accept a restrictive regulatory framework. The State, aware of the central role of the financial system and in particular


M Verset

S Palierne

D Mathon

P Swider

A Autefage

Comparison of the effect of locking vs standard screws on the mechanical properties of bone-plate constructs in a comminuted diaphyseal fracture model

Keywords:

Introduction

Healing of comminuted diaphyseal fractures is a major consideration in orthopaedics as they are frequently encountered, demonstrate a high rate of complications and their treatment is often challenging. They are often treated by bridging osteosynthesis for which the implant must withstand all weight-bearing forces until sufficient bridging callus is formed. One of the latest available implant in this indication is the Locking Compression Plate (LCP) whose combined holes accept either standard or locking screws. Although there are a few clinical and biomechanical studies comparing LCP plates featuring locking screws with non-locking plates, the real advantage of locking screws remains undefined and unquantified. The purpose of this ex vivo study was to compare the mechanical properties of bone-plate constructs with LCP plates used either with standard screws or with locking screws on an experimental model of comminuted fracture.

Methods

Twelve pairs of ovine tibia were harvested and packed with gauze soaked in isotonic saline solution before freezing (-24°C). After thawing at room temperature, they were kept moistened throughout the experiment. Inclusion criteria were skeletally mature animals belonging to one single breed, similar size of tibia and absence of bone diseases evaluated on radiographs. They were randomly divided into 2 equal groups. A model of comminuted fracture (mid-diaphyseal 5-mm gap) was created on the left tibia from each pair and treated with a 8-hole, 4.5-mm, broad stainless LCP plate with 3 bicortical self-tapping screws in each fragment. In group 1 (n=6), 4.5 mm cortical screws were placed in slightly inner eccentric position (to avoid collapse of the osteotomy site during weight-bearing). In group 2 (n=6), 5.0 mm locking screws were used. All screws were tightened using a torque-limiting screwdriver at 4 Nm. Biomechanical evaluations were performed by nondestructive tests at quasi-static displacement rate (1 mm/min) on electromechanical systems. Four-point bending, torsion and axial compression loading conditions were applied one after the other on plated bones and on intact contralateral bones, to serve as a control. Maximum load used for nondestructive tests was about 50% of yield load, as previously assessed by destructive tests on pre-test plated bones. Bending was performed in a lateromedial direction with upper anvils surrounding bone gap. After embedding of proximal and distal ends in polyurethane casting resin, bones sustained clockwise torsional load, then axial compression load. For bending and compression on plated bones, 2 monocortical 1.5 mm pins were seated through the lateral cortex (2.5 mm outside the edges of bone osteotomy). A laser scan micrometer allowed continuous measurement of width between pins during tests. Crosshead displacement, load, angle of rotation, torque and width between pins were recorded at 10 Hz. Extrinsic stiffness of bone-plate constructs (K) was calculated, as well as stiffness loss (Kr) compared with contralateral tibia. Slope of the load-gap displacement curve (S) was also calculated. K and Kr provide information on global mechanical properties of plated or intact bone, whereas S is a reflection of interfragmentary motion during load thus providing information on local mechanical properties close to the osteotomy gap. Results were statistically compared between the 2 groups by a 2-way ANOVA and Tukey's Post Hoc tests, for each loading condition with significance set at P<.05.

Results and Discussion

In 4-point bending, there were no significant differences between group 2 (G2) and group 1 (G1) for K (G2: 321.9 ± 65.2 kN/m, G1: 286.0 ± 36.6 kN/m), for Kr (G2: 55.4 ± 10.4%, G1: 64.5 ± 3.9%) and for S (G2: 292.0 ± 84.3 N/mm, G1: 271.4 ± 36.2 N/mm). In torsion, there were no significant differences between the 2 groups for K (G2: 133.3 ± 18.7 Nm/rad, G1: 117.2 ± 18.0 Nm/rad) and for Kr (G2: 44.0 ± 10.3%, G1: 55.0 ± 10.6%) (table 1).

Bending stiffness and torsion stiffness were not significantly different using locking screws or standard screws. That is consistent with most other in vitro and ex vivo studies comparing LCP with non locking (LC-DCP) plates [START_REF] Aguila | In Vitro Biomechanical Comparison of LC-DCP and LCP[END_REF] [START_REF] Snow | A Mechanical Comparison of the LCP and the LC-DCP in an Osteoporotic Bone Model[END_REF]. In compression, group 2 showed significantly lower K (611.1 ± 104.0 kN/m) and higher Kr (66.5 ± 10.3%) than group 1 (1019.2 ± 249.5 kN/m; 47.7 ± 10.8%) (table 1, figure 1). Compression stiffness with locking screws was about half compared with standard screws, whereas other studies showed significantly higher stiffness for locking screws [2] [3]. It might be related to 2 phenomena: i) the friction forces induced by the screws which compress the plate onto bone in standard osteosynthesis and ii) the limitation of bone displacement by the eccentric position of standard screws that are blocked on the inner part of the plate hole under axial compression whereas standard screws are usually placed in central position. Anyway, there was no significant difference between the 2 groups for S (G2: 254.6 ± 72.6 N/mm, G1: 438.2 ± 228.4 N/mm), meaning that the significant difference of global mechanical properties seems to have no significant effect on the local mechanical properties (table 1). Asterisks indicate significant differences between groups (P<.05). Whiskers lower and upper limits = 2.5th and 97.5th percentiles.

The main limitation to this ex vivo study is the only mechanical evaluation of bone-plate constructs, without assessment of bone healing. Now, bone healing results both of controlled mechanical conditions and of favourable biological conditions at the fracture site. Further in vivo study is needed to compare the biological conditions of bone-plate constructs with LCP plates used either with standard screws or with locking screws. It may be conducted by assessing the mechanical properties of bone callus after bridging osteosynthesis according to the same experimental design.

Conclusions

Locking screws had no statistically significant effect on the mechanical properties of LCP-plated bones in 4-point bending and torsion, compared to standard screws. In axial compression, locking screws induced a significant decrease in global mechanical properties without significant decrease in local mechanical properties close to the osteotomy gap. Our mechanical ex vivo study, completed by further in vivo study, should help to make a rational choice of the type of implant to treat comminuted fractures.

KFigure 1

 1 Figure 1 Box plots comparing mechanical properties in axial compression for the 2 groups:

Table 1

 1 Mechanical properties of bone-plate constructs for each type of condition (mean ± SD)

		Standard screws (G1) Locking screws (G2)
		K	Kr	S	K	Kr	S
	4-point bending	286 007.22 ±	64.47 ±	271.35 ±	321 926.90 ±	55.44 ±	292.00 ±
		36 586.22	3.87	36.16	65 244.02	10.39	84.33
	Torsion	107.28 ±	54.98 ±	/	122.07 ±	44.01 ±	/
		16.46	10.56		17.10	10.27
	Axial compression 1.02E+6 ±	47.67 ±	438.24 ±	611 057.11 ±	66.50 ±	254.61 ±
		249 501.43	10.77	228.34	104 012.99	10.26	72.56


Anne-Marie Kermarrec
email: akermarrec@inria.fr

Afshin Moin
email: afshin2927@yahoo.com

FlexGD : A Flexible Force-directed Model for Graph Drawing

We propose FlexGD, a force-directed algorithm for straightline undirected graph drawing. The algorithm strives to draw graph layouts encompassing from uniform vertex distribution to extreme structure abstraction. It is flexible for it is parameterized so that the emphasis can be put on either of the two drawing criteria. The parameter determines how much the edges are shorter than the average distance between vertices. Extending the clustering property of the LinLog model, FlexGD is efficient for cluster visualization in an adjustable level. The energy function of FlexGD is minimized through a multilevel approach, particularly designed to work in contexts where edge length distribution is not uniform. Applying FlexGD on several real datasets, we illustrate both the good quality of the layout on various topologies, and the ability of the algorithm to meet the addressed drawing criteria.

INTRODUCTION

Force-directed algorithms [START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF][START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF][START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF][START_REF] Noack | Energy models for graph clustering[END_REF][START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Koren | The binary stress model for graph drawing[END_REF] are one popular approach to graph drawing. They model vertices as a collection of particles and assign them attractive and repulsive forces according to force shapes improvised from physical metaphors like springs and electrical charges. The algorithm lays out the graph from an initial random configuration computing the net force on each vertex and moving the vertices iteratively until an equilibrium state is achieved between all forces. Force-directed algorithms are composed of two components: the energy function and the minimization algorithm. The energy function assigns a scalar energy value to the layout. Attractive and repulsive forces are linked to the energy function as force is the minus gradient of energy. The role of the minimization algorithm is to compute a force equilibrium in the system, being equivalent to a local minimum of the energy function.

Attractive and repulsive forces (or equivalently the energy function) are defined in the goal of meeting some aesthetic criteria of drawing like uniform edge length and minimum edge crossing. For example, the Spring-Electrical model [START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF] enforces uniform edge length while the Stress model [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF] estimates the Euclidean distance between vertices on the layout with their graph-theoretic distance. Recently, Noack [START_REF] Noack | Energy models for graph clustering[END_REF] has investigated the influence of the shape of attraction and repulsion energies 1 on the clustering properties of a model. The author shows that Linear attraction and Logarithmic repulsion energies are better for cluster visualization than previously considered energy functions. The LinLog model is consequently proposed, and some of its properties are derived.

In this paper, we suggest FlexGD, a Flexible force-directed algorithm for Graph Drawing. FlexGD draws graphs according to the two criteria of uniform vertex distribution and structure abstraction. The model is flexible, in that it is parameterized to be biasable towards any of the two drawing criteria, according to user preferences. The core idea is to use both attractive and repulsive forces to distribute the vertices over the drawing area. More specifically, we replace the pairwise logarithmic repulsion energy of the LinLog model with linear-logarithmic energy, while preserving the linear attraction of edges intact. This modification has multiple advantages. First, the drawing area is filled optimally and the layout looks pleasing in the frontiers. Second, it upgrades the cluster visualization property of LinLog to abstractable cluster visualization, i.e. the user can decide upon the density of the clusters and to what extent they are set apart. FlexGD is also capable of drawing disconnected graphs while most of the previous models have difficulties with their handling.

Existing minimization algorithms are in general designed for energy functions creating a rather uniform edge length distribution. FlexGD (like LinLog) may give rise to layouts with very uneven edge lengths. To overcome this challenge we suggest a sophisticated multilevel algorithm with exact parameterization methods to minimize the FlexGD energy function. A slightly modified version of this algorithm can be used to find LinLog minimum energy layouts. This is particularly important as no algorithm is proposed in [START_REF] Noack | Energy models for graph clustering[END_REF] for finding the LinLog layouts of large graphs. We present FlexGD layouts of some large real datasets to illustrate that the algorithm can generate quality layouts in a wide range of abstraction, satisfying different user preferences. At the end, some properties of FlexGD minimum energy layouts are analytically derived.

RELATED WORK

Force-directed algorithms [START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF][START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF][START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF][START_REF] Noack | Energy models for graph clustering[END_REF][START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Koren | The binary stress model for graph drawing[END_REF] have been in use for years and many derivations of them are applied in industry and academia. In this section, we mention a number of important works and approaches to graph drawing, although the literature we discuss is by no means comprehensive.

The initial versions of force-directed models suffered from high running time. A survey of these models is available in [START_REF] Tollis | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF]. The main source of complexity is the computation of pairwise forces. The Barnes and Hut algorithm [START_REF] Barnes | A hierarchical o(nlogn) force-calculation algorithm[END_REF] alleviated this problem by estimating the repulsion force of close vertices which are sufficiently far from the active vertex as a whole. With the advent of the multilevel algorithms [START_REF] Walshaw | A multilevel algorithm for force-directed graph drawing[END_REF][START_REF] Harel | A fast multi-scale method for drawing large graphs[END_REF][START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF][START_REF] Koren | Ace: a fast multiscale eigenvectors computation for drawing huge graphs[END_REF], force-directed algorithms became rather efficient both from the computational and the quality points of view. Harel and Koren suggest a different approach called High Dimensional Embedding (HDE) [START_REF] Harel | Graph drawing by high-dimensional embedding[END_REF] for graph drawing. HDE relates the Euclidean distance between the vertices to their graphtheoretic distance in a high-dimensional space. It then projects the vertices back to the 2-dimensional space using Principal Component Analysis (PCA). Another line of work which has recently become popular is spectral graph drawing [START_REF] Koren | Ace: a fast multiscale eigenvectors computation for drawing huge graphs[END_REF][START_REF] Koren | Drawing graphs by eigenvectors: theory and practice[END_REF][START_REF] Puppe | Spectral Graph Drawing: A Survey[END_REF]. The idea is to use the (generalized) eigenvectors of the Laplacian/Adjacency matrix of the graph as the drawing. Algebraic multi-scale Computation of Eigenvectors (ACE) [START_REF] Koren | Ace: a fast multiscale eigenvectors computation for drawing huge graphs[END_REF] uses the smallest eigenvectors of the Laplacian as the drawing. The algorithm is combined with a multilevel coarsening scheme to obtain a sophisticated initialization of the eigenvectors. Despite very low execution time, the quality of HDE and spectral layouts is usually lower than the quality of layouts computed by force-directed algorithms [START_REF] Hachul | An experimental comparison of fast algorithms for drawing general large graphs[END_REF].

We are motivated to suggest FlexGD as a robust model to graph drawing because it can generate a spectrum of layouts encompassing from conventional force-directed layouts to clustered layouts of LinLog. Comparing with each individual model, FlexGD layouts seem to be nicer and more symmetric. Furthermore, in huge irregular sparse graphs, FlexGD reveals the community structure better than other models. This is helpful for visualization of graphs arising from applications like web connectivity and email networks.

Beside links to LinLog, our model has also similarities with the Binary Stress Model of Koren and C ¸ivril [START_REF] Koren | The binary stress model for graph drawing[END_REF]. The Binary Stress Model bridges the Stress [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF] and the Spring-Electrical [START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF] models. It has also the property of abstractability. However, apart from its major differences from FlexGD both in the energy function and in the optimization technique, we believe that, as it will be shown in the paper, linear attraction and linear-logarithmic pairwise energy functions of FlexGD makes it more efficient in uniform vertex distribution and in cluster visualization. For example, the frontiers of the Binary Stress layouts are denser than the center. The authors add a random perturbation improving occasionally this drawback. Such a problem does not arise with FlexGD, as the linear-logarithmic shape of the pairwise forces result in perfectly even distribution of the vertices over the drawing area (see Figure 1).

DEFINITIONS AND NOTATIONS

A d-dimensional layout p of a graph G = (V, E) is a mapping of vertices into the Euclidean space p : V -→ R d , where every u ∈ V is assigned with a coordinate vector pu. The Euclidean distance between u and v is denoted by pu -pv . We will use some notions from the literature on graph clustering to express the properties of FlexGD. The cut and the density are two measures widely used as the coupling between two subgraphs. Minimizing the coupling is an established technique in graph clustering [START_REF] Luxburg | A tutorial on spectral clustering[END_REF][START_REF] Schaeffer | Graph clustering[END_REF]. The cut between two disjoint vertex sets V1 and V2 is defined as cut[V1, V2] = |EV 1 ×V 2 |, where EV 1 ×V 2 represents the set of edges between V1 and V2. Using the cut as a coupling measure has the disadvantage of selecting biased clusters, i.e. one huge cluster against a tiny one. This is undesirable as clusters are supposed to contain a reasonably large group of vertices. One way to bypass this problem is to penalize small clusters by dividing the cut by the size of clusters. This leads to the definition of density:

density(V1, V2) = cut[V 1 ,V 2 ]
|V 1 ||V 2 | . Arithmetic, geometric and harmonic mean are the most popular definitions in the literature to measure the mean distance between a set of vertices. For layout p and F ⊂ V (2) , where V (2) represents the set of vertex pairs, we represent arithmetic, geometric and harmonic mean of F on p by arith(F, p), geo(F, p) and harm(F, p) respectively. They are defined as:

arith(F, p) = 1 |F | {u,v}∈F pu -pv . geo(F, p) = |F | {u,v}∈F pu -pv . harm(F, p) = |F | {u,v}∈F 1 pu-pv .
In FlexGD, attractive forces are reinforced by an abstraction constant. Hence, we found it helpful to generalize the definition of the arithmetic mean in order to write the theorems in a more readable form. The weighted arithmetic mean is defined as:

arith k+ (F, p) = {u,v}∈F λuv pu -pv {u,v}∈F λuv , λuv = k + 1 if {u, v} ∈ E F 1 otherwise ,
where E f is the set of edges over F .

FLEXGD ENERGY FUNCTION

For layout p of a graph G = (V, E), many of the known energy models [START_REF] Noack | Energy models for graph clustering[END_REF][START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF] have the following form:

U (p) = {u,v}∈E f ( pu -pv ) + {u,v}∈V (2)
g( pu -pv ),

where f ( pu -pv ) is associated with the attraction of edges, and g( pu -pv ) with the repulsion between all pairs of vertices. The minus gradient of f and g determines the attractive and repulsive forces. In the LinLog model, the energy function for layout p is defined as:

ULinLog(p) = {u,v}∈E pu -pv - {u,v}∈V (2)
ln pu -pv .

For layout p and the abstraction constant k, the FlexGD energy function is defined as:

U (p, k) = {u,v}∈E k pu -pv + {u,v}∈V (2)
( pu -pv -ln pu -pv ).

(

) 2
The first term captures the graph structure by shortening the edges, while the second term distributes the vertices evenly over the drawing surface. In models like [START_REF] Noack | Energy models for graph clustering[END_REF][START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF], g is monotonically decreasing. As a result, disconnected vertices are likely to repulse each other towards infinity. On the contrary, both attractive and repulsive components are present in g of FlexGD. Hence, disconnected vertices rest in a finite neutral distance from each other, explaining why FlexGD can draw even totally disconnected graphs. Parameter k determines how much the edges must be shorter with respect to the mean neutral distance. Figure 1 shows how a graph is uniformly packed within a circular drawing area regardless of its connectivity. The attractive force of the edges and the pairwise force exerted on a vertex u from another vertex v are:

∀{u, v} ∈ E, fa(u, v) = k(pv -pu) pv -pu , (3)
∀{u, v} ∈ V (2) , fr(u, v) = (1 - 1 pv -pu ) • (pv -pu) pv -pu . (4)
The overall force exerted on u from v is then fa + fr.

It is proved that adding multiplicative constants to the attractive and repulsive terms of previous energy models does not change the minimum energy layout, but only scales it (see [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF] for example). However, the minimum energy layout of FlexGD changes with k. This gives FlexGD the flexibility of drawing layouts in different levels of abstraction. Figure 2 shows the layout of an email network containing 265214 vertices and 420045 edges. Edges are not represented for more clarity. The abstraction constant is chosen as k = 4000 in Figure 2a. The clustered nature of this webmail graph is clear in this figure. One may choose to abstract the layout more at the price of viewing less details. The layout of the same graph is shown in Figure 2b for k = 20000.

Figure 2 also demonstrates two further assets of FlexGD layouts. First, there is an empty space around clusters. It is very helpful in distinguishing the frontier between them. These clusters are particularly meaningful in social networks or web graphs, where they represent friendship groups or societies. This effect is due to the intra-distance between the vertices of a cluster being small with respect to their average distance from the rest of the graph. Consequently, they act as supernodes with high mass, exerting strong repulsion to the outside vertices pushing them further from the community. This effect increases with k, as the clusters get denser for higher k. Second, disconnected vertices are put towards the frontiers. This prevents them from adding visual noise to the connected components of the graph.

MINIMIZATION OF FLEXGD ENERGY FUNCTION

The minimum of the FlexGD energy function can be found using an iterative algorithm. In each iteration, the net force exerted on each vertex is computed. The vertices are then moved in the direction of this force by some step length until the layout change is less than some tolerance. Previous works [START_REF] Walshaw | A multilevel algorithm for force-directed graph drawing[END_REF][START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF][START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF] apply a force-directed algorithm with an adaptive step length. The algorithm starts with an initial global step length and decreases it per cycle. This scheme works well, if the edge length distribution is not very uneven. In FlexGD this assumption is violated, specifically if a large level of abstraction is applied, i.e. k is set to a large value. This issue can be treated by applying a vertex specific adaptive step length. In each iteration, the current direction of the net force exerted on a vertex is compared with its previous direction. The step length is then increased or decreased proportional to the change of direction. Our force algorithm is given in Algorithm 1.

Since the force algorithm works on top of a multilevel coarsening scheme (see below), it is important that the initial step length is small enough, otherwise the usefulness of the layout resulting from the previous coarsening level is destroyed. We compute a graphspecific initial step length with an empirical equation derived from the following theorem:

Algorithm 1 ForceAlgo(Y,G,k, ) 1: X ← Y
Y is the initial guess from the previous round of the multilevel algorithm.

2: ratio ← 2.0 (> 1 + ) 3: γ ← 0.5 4: d0 ← 0.00000001 small float. 5: s0 ← |V | 2 k(k|E|+|V | 2 )
graph-dependent initial step length. 6: ∀i ∈ V : si ← s0 7: fu ← random 8: while (ratio > 1 + ) do 9:

BH(X)

computing the Barnes and Hut tree on the current layout. for i ∈ V do 12:

x 0 i ← xi, f 0 i ← fi 13: ∀j ∈ V, j ↔ i : fi = fi + fa(i, j) compute attractive forces of edges. 14: ∀j ∈ V, j = i, fi = fi + fr(i, j)
compute pairwise forces. This computation is accelerated using the Barnes and Hut scheme.

15: si = si + si * ( f i f i • f 0 i f 0 i ) * γ
modify the step length proportional to the change of direction of the net force.

16:

xi = xi + si * ( f i f i
) move the active vertex. 17:

d = d + xi -x 0 i 18:
end for

19: ratio ← max ( d d 0 , d 0 d ) halt when the change of layout is negligible. 20: d0 ← d 21: end while Theorem 5.1 If p 0 is a drawing of a graph G = (V, E) with minimum FlexGD energy then: k {u,v}∈E pu -pv + {u,v}∈V (2) pu -pv = V (2) .
Proof Suppose p 0 is a drawing with minimum FlexGD energy. If we multiply all coordinates in p 0 by d ∈ R, the energy of the system is: (2) d pu -pv -ln d pu -pv .

U (d, p 0 ) = {u,v}∈E d pu -pv + {u,v}∈V
Since p 0 is a drawing with minimum energy, this equation has a minimum at d = 1, that is:

U (d, p 0 ) = {u,v}∈E pu -pv + {u,v}∈V (2)
pu -pv -

V (2) d , U (d = 1, p 0 ) = {u,v}∈E pu -pv + {u,v}∈V (2)
pu -pv -V

(2) = 0.

We can rewrite the left side of this theorem in the form of is a value between ē and d. Dividing further by k gives a value of the order of the mean edge length. Setting the initial step length to l/k always led to satisfactory results for the graphs we tried. Further modification of the step length is done on a per vertex basis through the adaptive step length scheme.

k |E| ē + |V | 2 d = (k |E|+|V | 2 )l,

The Barnes and Hut Algorithm

A direct application of Algorithm 1 is not effective for large graphs, because its complexity is O(|E| + |V | 2 ). A common practice in graph drawing (like [START_REF] Quigley | Fade: Graph drawing, clustering, and visual abstraction[END_REF][START_REF] Koren | The binary stress model for graph drawing[END_REF][START_REF] Tunkelang | Jiggle: Java interactive graph layout environment[END_REF]) is to decrease the complexity to O(|E| + |V | log |V |) using the Barnes and Hut scheme [START_REF] Barnes | A hierarchical o(nlogn) force-calculation algorithm[END_REF]. The idea is to speed up the calculation of pairwise forces by regrouping the nearby vertices and computing their force as a whole, provided their center of mass is far enough from the active vertex. This is done through recursively assigning the vertices to the nodes of a quadTree, where each node has at most four children. There is some mass, a center and a square area associated with each node. Vertices are inserted one by one into the tree, starting from the root node. If the current node already contains a vertex, the corresponding area is divided into four squares known as quads. The new vertex is consequently inserted into the right quad, and the mass and the center of the parent node are updated as follows:

x = (m • x + mi • xi)/(m + mi), m = m + mi,
where m and x are the mass and the center of the node, and mi and xi the mass and coordinates of the inserted vertex, respectively. This procedure is iterated until all vertices are inserted, and there is only zero or one vertex in each external node. Figure 3 illustrates the formation of a quadTree. We form the quadTree once in the beginning of each execution cycle. When computing the pairwise forces, all the vertices of a node are approximated as a single vertex if s/d < θ, where s is the width of the area represented by the quad of the corresponding node, and d the distance of the active vertex from the quad center. In our setting we set θ = 0.5.

A Multilevel Algorithm

The force algorithm (Algorithm 1) finds a local minimum of the energy function. Consequently, it is not very probable that it results in satisfactory drawings of large graphs as their energy functions have many local minima. In addition, too many cycles are needed to create a stable drawing out of the initial configuration. Multilevel algorithms can greatly alleviate these problems by consecutively coarsening a graph G0 into coarser graphs G1, ..., Gn. The layout of the coarsest graph is computed cheaply as it is very small. The computed coordinates are then promulgated to the finer graph. The finer graph usually needs less modifications as it is already in a rather good shape.

Edge Collapsing (EC) [START_REF] Gupta | Highly scalable parallel algorithms for sparse matrix factorization[END_REF][START_REF] Walshaw | Parallel dynamic graph partitioning for adaptive unstructured meshes[END_REF][START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF] is one widely-used coarsening strategy in graph drawing. This method works based on a Multiple Independent Edge Set (MIES). An independent edge set is a set of edges no two of which are adjacent to the same vertex. It is maximal, if adding any new edge to the set destroys the independence. MIES can be computed through a greedy algorithm. Namely, all vertices are unmatched in the beginning. An unmatched vertex is picked up at random, and is merged with one of its unmatched neighbors. As a result of this merging, the edge between them is collapsed. Both merged vertices are then marked as matched. If the vertex has no neighbors (i.e. it is disconnected from the rest of the graph), it is marked as matched without being merged. The algorithm iterates until no vertex remains unmatched.

The success of a coarsening scheme depends on the graph topology. For example, we observed that for graphs with hollow topology, EC has difficulties escaping the local minima. In addition, for some graphs the coarsening is very slow, i.e. the number of vertices in the coarser graph is close to the number of vertices in the finer graph. Consequently, we followed [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF] by adapting an alternative coarsening strategy based on Multiple Independent Vertex Set (MIVS). A multiple independent vertex set is a set of vertices no two of which are directly connected by an edge. It is maximal, if adding any new vertex to the set leads to violation of the independence condition. When coarsening with MIVS, an edge is added between two vertices of the coarser graph, if the distance apart between the corresponding vertices of the finer graph is no more than three. MIVS coarsens more aggressively than EC, that is, the number of vertices in the coarser graph is much smaller (usually less than 50%) than the number of vertices in the finer graph. The drawback of MIVS is that the number of edges in the coarser graph is sometimes very high. This issue increases the memory and time complexity of the algorithm. Figure 4 shows the result of coarsening a 30 by 30 grid through MIVS and EC coarsening strategies.

In [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF], edges are computed using the Galrekin product of the prolongation matrix P and the adjacency matrix of the finer graph A f (see [START_REF] Hu | A multilevel algorithm for wavefront reduction[END_REF] for more details). The Galerkin product is defined as P T A f P . We found that computing this product is expensive for large graphs. In our implementation, we first connect all the vertices in the MIVS, if their graph theoretical distance is 2. For distances equal to 3, we iterate on the edges, and for those whose neither of their end points is in the MIVS, check the neighbors of their end points. An edge is added between the two MIVS neighbors of the end points, if there is already no edge between them. This strategy works faster than computing the Galerkin product.

The prolongation of coordinates from the coarser graph to the finer graph is done as follows. If the coarser graph is issue of EC, each vertex of the finer graph corresponds to exactly one vertex of the coarser graph. In this case, the coordinates of the coarser graph are attributed directly to the corresponding vertices of the finer graph. If the coarser graph rises from MIVS, each vertex of the finer graph is either in the multiple independent vertex set or has at least one neighbor in that. In the former case, the coordinates are taken directly from the corresponding vertex of the coarser graph. In the latter, the coordinates are computed as the mean of the coordinates of the neighbors in the multiple independent vertex set. Since some vertices may have the same coordinates in the fine graph, we add some small random displacement to set them apart.

We implemented a hybrid coarsening algorithm. Our default strategy is Heavy Edge Collapsing (HEC) [START_REF] Walshaw | Parallel dynamic graph partitioning for adaptive unstructured meshes[END_REF][START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF]. Namely, each active vertex is merged with an unmatched neighbor corresponding to the heaviest incident edge, and the edge between them is collapsed. In few cases where the result of HEC was not good enough, we used an alternative coarsening strategy based on a Multiple Independent Vertex Set (MIVS) [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF]. In this strategy, the coarser graph is built by choosing an MIVS from among the vertices of the finer graph. Then, an edge is added between each two vertices if their graph-theoretic distance apart is no more than 3. For implementation details about the coarsening and the prolongation phases of HEC and MIVS refer to the technical report provided in [anonymized]. We stop coarsening if one of the following happens. First, the level of coarsening is more than a predefined threshold. In our setting we do not coarse more than 12 levels. Second, the coarsening ratio is too high. This ratio is defined as the number of connected vertices in the coarser graph by the number of connected vertices in the finer graph. We set this threshold to 0.9. Finally, the number of the remaining connected vertices is less than a minimum. We set this to 10.

PROPERTIES OF FLEXGD MINIMUM ENERGY LAYOUTS

In this section, we derive some properties of FlexGD minimum energy layouts. The goal is to understand quantitatively how the model makes a tradeoff between the two drawing criteria, and how it separates the clusters by tweaking k.

Theorem 6.1 states that FlexGD finds the best compromise between maximizing the geometric mean and minimizing the weighted arithmetic mean distance between all vertices. This property is responsible for shortening the edges and lengthening the non-edges. If the graph contains no edges, the weighted arithmetic mean is equal to the usual arithmetic mean. The maximum of the ratio is then one, as it is a well-known fact from AM-GM inequality that the geometric mean is always greater than or equal to the arithmetic mean. The maximum is achieved when all distances are equal. Though in the 2-dimensional space equality is impossible for more than 3 vertices because of geometric constraints. Consequently, the model distributes the vertices uniformly in order to maximize the ratio by closing the two means as much as possible. This property explains why the vertices have a perfectly even distribution over the drawing area in Figure 1a. When edges reside in the graph, connected vertices are put closer to each other. The reason is they are weighted more in the weighted arithmetic mean. Therefore, their further shortening, up to some extent controlled by k, decreases the weighted arithmetic mean more than it increases the geometric mean. Theorem 6.1 The minimization of the FlexGD energy function is equivalent to the minimization of arith k+ (V (2) ,p) geo(V (2) ,p) .

Proof Let p 0 be a layout with minimum FlexGD energy. If {u,v}∈E p 0 u -p 0 v + {u,v}∈V (2) p 0 u -p 0 v = c, then p 0 is a solution to: minimize(-{u,v}∈V (2) ln pu -pv ) subject to {u,v}∈E pu -pv + {u,v}∈V (2) pu -pv = c.

Model Minimization equivalence

One-dimensional bipartition abstractable LinLog [START_REF] Noack | Energy models for graph clustering[END_REF] minimize

arith(E,p) geo(V (2) ,p)

harm(V 1 × V 2 , p 0 ) = 1 density(V 1 ,V 2 )

NO

FlexGD minimize arith k+ (V (2) ,p) geo(V (2) ,p)

harm(V 1 × V 2 , p 0 ) = 1 1+k * density(V 1 ,V 2 )

YES

Table 1: Summary of some properties of FlexGD and LinLog.

The above expression may be reformulated in the form of minimize -ln(geo |V (2) | (V (2) , p)). Since |V (2) | exp(x) is an increasing function of x, the minimization of this expression is equivalent to minimize exp(ln 1 geo(V (2) ,p) ). Multiplying the numerator by the constant arith k+ (V (2) , p), and rewriting the restriction, we obtain: minimize arith k+ (V (2) , p) geo(V (2) , p) subject to arith k+ (V (2) , p) = c |E| + |V (2) | .

Suppose there exists a layout q 0 of G with minimum FlexGD energy for which arith k+ (V (2) ,q 0 ) geo(V (2) ,q 0 ) < arith k+ (V (2) ,p 0 ) geo(V (2) ,p 0 )

. We can always define a scaling q 1 = c (|E|+|V (2) |)arith k+ (V (2) ,q 0 ) q 0 for which

arith k+ (V (2) , q 1 ) = c |E|+|V (2) | , but
arith k+ (V (2) ,q 1 ) geo(V (2) ,q 1 ) = arith k+ (V (2) ,q 0 ) geo(V (2) ,q 0 )

< arith k+ (V (2) ,p 0 ) geo(V (2) ,p 0 )
. This is a contradiction. Hence q 0 does not exist and the restriction may always be removed. Theorem 6.2 posits that in 1-dimensional FlexGD layouts of bipartitions, the distance between the two partitions of a graph decreases with k times their density. This theorem does not generalize to more than one dimension, but remains approximately true for 1+ dimensional layouts of clusterizable bipartitions. Refer to Appendix A for more details of the approximation. For graphs containing a higher number of clusters, there is in general no 2D or 3D drawing where distance between every two clusters obeys the same equation, without violating the triangle inequality w.r.t. a third cluster. Despite this, Theorem 6.2 illustrates the logic behind the separation of clusters in FlexGD layouts. Theorem 6.2 Let p 0 be a one-dimensional drawing of the graph G = (V, E) with minimum FlexGD energy. Let (V1, V2) be a bipartition of V such that the vertices in V1 have smaller positions than the vertices in V2 (i.e. ∀v1 ∈ V1, ∀v2 ∈ V2 :

pv 1 < pv 2 ). Then, harm(V1 × V2, p 0 ) = 1 1+k * density(V 1 ,V 2 ) .
Proof Let p 0 be a layout with minimum FlexGD energy. If we add d ∈ R to the coordinates of the vertices of V1 in a way that the largest coordinate of the vertices in V1 remains less than the smallest coordinate of the vertices in V2, the FlexGD energy becomes:

U (d, p 0 ) = {u,v}∈E V (2) 1 ∪E V (2) 2 k |pu -pv| + {u,v}∈V (2)
1 ∪V

(2) 2

|pu -pv| -ln |pu -pv|

+ {u,v}∈E V 1 ×V 2 k(|pu -pv| + d) + {u,v}∈V 1 ×V 2 |pu -pv| + d -ln(|pu -pv| + d).
Since p 0 is a layout with minimum energy, the above function has a minimum at d = 0, i.e. U (d = 0, p 0 ) = 0. Then:

k |EV 1 ×V 2 | + |V1 × V2| = + {u,v}∈V 1 ×V 2 1 |pu -pv| .
Replacing the right side with

|V 1 ||V 2 | harm(V 1 ×V 2 ,p 0 ) and |V1 × V2| with |V1| |V2|
, the result is directly obtained. While Theorem 6.1 explains how convex subgraphs are clustered in the FlexGD layouts, Theorem 6.2 is responsible for the separation of clusters as a function of their coupling. This suggests the definition of clustering, where vertices inside a cluster must be as similar as possible, while being dissimilar from vertices of the other clusters. At this point, we would like to add that extra parameters do not give more features to the model. Theorem 6.3 formalizes this finding for a set of abstraction constants {k1, k2, k3}:

Theorem 6.3 The minimum of U = {u,v}∈E k1 pu -pv + {u,v}∈V (2) k2 pu -pv -k3 ln pu -pv , is equal to the mini- mum of U = {u,v}∈E k 1 k 2 pu -pv + {u,v}∈V (2) pu -pv - ln pu -pv up to scaling by k 3 k 2 .
Proof If we scale the layout by k 3 k 2 , the energy of Unew is:

Unew = {u,v}∈E k1k3 k2 pu -pv + {u,v}∈V (2) k3k2 k2 pu -pv -k3 ln k3 k2 pu -pv .
This can be rewritten as:

Unew = k3( k1 k2 {u,v}∈E pu -pv + {u,v}∈V (2)
pu -pv -ln pu -pv ) +

V (2)
k3 ln k3 k2 .

Since k3 is positive and V (2) k3 ln k 3 k 2 is a constant, the minimum of this function is the same as the minimum of

k 1 k 2 {u,v}∈E pu - pv + {u,v}∈V (2) pu -pv -ln pu -pv .
This theorem states that the effect of k3 is limited to scaling, having merely a zooming effect. Furthermore, apart from its scaling effect, k2 only changes the abstraction constant to k 1 k 2 . Since every positive real value can be chosen directly as the abstraction constant, adding k2 has no mathematical advantage. Table 1 compares the two properties of FlexGD expressed by Theorem 6.2 and Theorem 6.1 with analogous results about LinLog taken from [START_REF] Noack | Energy models for graph clustering[END_REF].

IMPLEMENTATION AND RESULTS

We have implemented a multi-threaded simulator based on Java, and used the visualization capabilities of the JUNG library [12]. Most of the graphs in this section are taken from the University of Florida Sparse Matrix Collection [START_REF] Davis | The University of Florida Sparse Matrix Collection[END_REF]. FlexGD is very sensitive to the correct calibration of the initial step length according to Theorem 5.1 and the value of the abstraction constant k. It reveals the structure of a graph provided k is large enough. We observed choosing k as o( |V 2 | |E| ) is a proper value, depending on the level of abstraction the user prefers. If the graph is disconnected, the biggest component may be considered. For very sparse graphs, where vertex degree distribution is very uneven, smaller values of k can also be used. Such graphs generally result from applications like social networking or web connectivity networks.

(i) jagmesh8, k = 900 (j) jagmesh8 (k) jagmesh8 (l) jagmesh8 (m) harvard500, k = 5 (n) harvard500, k = 20 (o) harvard500, k = 100 (p) harvard500 (q) harvard500 (r) harvard500
Figure 5 compares the FlexGD layouts of a few graphs with the layouts of some other force-directed algorithms. Davidson and Harel [START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF] suggest an energy function resulting in more uniform vertex distribution. Spring-Electrical [START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF] is one of the most popular energy functions enforcing rather uniform edge length. Although these models are popular, the minimization algorithms suggested in the original papers are no more applied as more advanced algorithms have been proposed. We applied the multilevel algorithm suggested by Walshaw [START_REF] Walshaw | A multilevel algorithm for force-directed graph drawing[END_REF] to find the minimum energy layouts of these models. Hence, we call them ML-SE and ML-DH standing for Multilevel Spring-Electrical and Multilevel Davidson and Harel. LinLog layouts are drawn with a variant of Algorithm [START_REF] Barnes | A hierarchical o(nlogn) force-calculation algorithm[END_REF] where FlexGD attraction and repulsion forces are replaced with those of LinLog. Furthermore, an initial step length proper to LinLog is used. This step length is estimated through the analogue of Theorem 5.1 for LinLog. The symmetries are shown well in the FlexGD layouts and the frontiers are decent. The distribution of vertices in FlexGD layouts is more uniform than the LinLog layouts. For smaller values of k, the FlexGD layouts are more similar to the layouts of the conventional models, while for larger values of k, they are closer to the LinLog layouts. This property is pretty interesting as one can draw a spectrum of layouts with different properties without changing the drawing model.

Figure 6 compares some other FlexGD sample layouts with the layouts of HDE and ACE. The running time of HDE and ACE is a few seconds. Though, their quality is generally much inferior to FlexGD layouts. As it is seen in Figures 5 and6, FlexGD has a satisfactory performance on regular grid-like graphs. Though its main usefulness is for the representation of huge sparse graphs with non-uniform vertex degrees distribution. Many conventional models have difficulties with giving useful insight into the community structure of such graphs, i.e. they usually result a little informative clutter of interconnected vertices. One example of such graphs was shown in Figure 2. Other examples are provided in Figure 7. We believe for such graphs, drawing in the goal of visualizing the community structure is more indicative than using the conventional drawing criteria.

It is also worth mentioning the running time of the algorithm increases with k. The reason is that higher values of k put connected vertices closer to each other. Consequently, the Barnes and Hut algorithm divides the space into smaller quads, meaning the quadTree becomes bigger. In addition, the force algorithm needs more iterations, because the layout must be refined in smaller distances necessitating smaller values of tolerance.

The execution time of the FlexGD algorithm is given in Table 2 for some sample layouts. For graphs in the first part of some tens of thousands of vertices, the execution time is a few minutes. This is a reasonable time considering the high quality of the layouts. The Barnes and Hut scheme and the multilevel strategy improve significantly the quality and the running time of the algorithm. The adaptive step length scheme increases occasionally the running time as for some topologies like hollow ring-like graphs the layout converges late. Though, this scheme is essential to capture the non-uniform distribution of the edge length. An example is the G49 graph with 3000 vertices for which the running time is almost the same as that of the 100 by 100 grid which is 3 times larger in size but has a regular grid structure. In the same way, cegb2919 has about the same number of vertices as G49 and even contains more edges, but the algorithm draws it in almost a quarter of the time it takes to draw G49. In our experiments, our objective was to obtain the highest layout quality possible. Hence, we set θ = 0.5 for the Barnes and Hut algorithm, and chose small values of tolerance. Of course, the running time of the algorithm depends on these settings. One can decrease the running time by choosing larger values of θ and tolerance if little distortion is tolerable in the underlying application. A collection of FlexGD layouts is provided in Figure 8. The properties of the graphs are given in Table 2. Interested readers may find more results and comparisons in Chapter 3 of [START_REF] Moin | Recommendation And Visualization Techniques For large Scale Data[END_REF].

(b) G49 (c) G49 (d) fxm3-6, k = 50 (e) fxm3-6 (f) fxm3-6 (g) cavity01, k = 15 (h) cavity01 (i) cavity01 (j) finance256, k = 3000 (k) finance256 (l) finance256 (m) crack, k = 2000 (n) crack (o) crack (p) Harvard500, k = 20 (q) Harvard500 (r) Harvard500

CONCLUSION

FlexGD allows the user to abstract the graph structure to a desired level, optimally filling a circular drawing. Consequently, tweaking the abstraction constant, a user has more chance to obtain her favorite drawing. It is suitable for cluster visualization and extends this property of the LinLog model. FlexGD is indeed an extension to LinLog which in behavior acts similar to the Binary Stress model. However, it enjoys the advantages of both models. On the vided by the conventional models.

FlexGD has the tendency to give a circular shape to the layouts. The circular layout is the natural legacy of using both attractive and repulsive forces to distribute the vertices over the layout. This design choice was originally made to give the abstraction capability to the model. If the width and the length of the graph structure are proportional, this is not a severe constraint, specifically because the circular shape of the layout decreases with k. Fortunately, the majority of real-world applications give rise to such graphs. However, in fewer cases where the length and the width of the graph are very disproportional (like the line graph in Figure 1b), the circular shape of the layout may disturb the graph structure by enforcing it to be packed into a disc. Though, one should note that very long-shaped structures (like a 20 × 400 grid) are known to be one of the most challenging types of topology for all models of graph drawing.

Most previous works adopt an empirical approach to validate their model. A distinguishing point of this work is to adopt a more formal approach initiated by Noack [START_REF] Noack | Energy models for graph clustering[END_REF]. Its other asset is the multilevel algorithm coping with the non-uniform distribution of the edge length and its model-dependent parameterization. Variant of this algorithm can be considered as a complement to [START_REF] Noack | Energy models for graph clustering[END_REF], as to date we are unaware of works reporting LinLog layouts of large graphs.

We only treated the case of unweighted graphs. Though, the model can be easily generalized for weighted graphs by integrating the edge weights into the attraction term of the energy function. This gives the following equation for FlexGD energy function of weighted graphs: (2) pu -pv -ln pu -pv , where ωuv is the edge weight between u and v. All the previous theorems remain correct, but the edge weights are added to the terms corresponding to edges. For some topologies, specially those containing star-shaped components, the beforementioned coarsening strategies are ineffective as the number of vertices of the coarser graph remains very close to that of the finer of graph. Hence, developing more robust coarsening schemes may be considered as a direction for future work. This problem is not particular to FlexGD, and has been reported by previous authors too [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF]. Nevertheless, FlexGD can reveal the structure of some clustered graphs much better than other models without needing any more advanced multilevel scheme. An example is the Gupta/gupta1 graph from the University of Florida Sparse Matrix Collection. The authors were forced to design a new coarsening scheme in [START_REF] Davis | The University of Florida Sparse Matrix Collection[END_REF] to reveal the three groups of vertices in the graphs. Interestingly, FlexGD reveals these clusters easily without any coarsening phase. Figure 9 shows the FlexGD layout of this graph in two levels of abstraction.

U (p, k) = {u,v}∈E kωuv pu -pv + {u,v}∈V

A DISTANCE INTERPRETABILITY IN 1+ DIMENSIONAL FLEXGD BIPARTITION LAYOUTS

In this appendix we explain the approximate generalizability of Theorem 6.2 to 1+ dimensions. The following theorem holds exactly for layouts with any number of dimensions: . If (V1, V2) is a bipartition of vertices in a way that ∀u ∈ V1 : pu ∈ S1, and ∀v ∈ V2 : pv ∈ S2, that is ∀u ∈ V1 : i aix u i < b and ∀v ∈ V2 : i aix v i > b, then:

{u,v}∈E V 1 ×V 2 k D i=1 (x u i -x v i ) pu -pv + {u,v}∈V 1 ×V 2 D i=1 (x u i -x v i ) pu -pv = {u,v}∈V 1 ×V 2 D i=1 (x u i -x v i ) pu -pv 2 .
Proof If we add some distance vector d = (d1, . . . , dD) to all vertices in V1 in a way that none of them enter S2, i.e. ∀u ∈ V1 : i ai(x u i + di) < b, the energy of the new drawing is:

U new = {u,v}∈E V (2) 1 ∪E V (2) 2 k pu -pv + {u,v}∈V 2 1 ∪V 2 2 ( pu -pv -ln pu -pv ) + {u,v}∈E V 1 ×V 2 k D i=1 (x u i -x v i + d i ) 2 + {u,v}∈V 1 ×V 2 ( D i=1 (x u i -x v i + d i ) 2 -ln D i=1 (x u i -x v i + d i ) 2 ).
The partial derivative of this function with respect to di is:

∂Unew ∂d i = {u,v}∈E V 1 ×V 2 k x u i -x v i + d i D i=1 (x u i -x v i + d i ) 2 + {u,v}∈V 1 ×V 2 ( x u i -x v i + d i D i=1 (x u i -x v i + d i ) 2 - x u i -x v i + d i D i=1 (x u i -x v i + d i ) 2
).

Since p is a layout with minimum FlexGD energy, the application of any non zero vector d must result in increase of energy. Then, the gradient vector of Unew must be zero when d = 0, that is ∀di :

∂Unew ∂d i = 0. Hence D i=1 ∂Unew ∂d i = 0. D i=1 ∂Unew ∂di = {u,v}∈E V 1 ×V 2 k D i=1 (x u i -x v i ) D i=1 (x u i -x v i ) 2 + {u,v}∈V 1 ×V 2 ( D i=1 (x u i -x v i ) D i=1 (x u i -x v i ) 2 - D i=1 (x u i -x v i ) (x u i -x v i ) 2 ) = 0.
For D-dimensional layouts of graphs, clusterizable to some extent, Theorem A.1 leads to the following useful corollary:

Corollary A.1 Let p be a D-dimensional drawing of G = (V, E) with minimum FlexGD energy. For any non-scaling linear transformation of the coordinate system 2 that partitions the vertices into (V1, V2) in a way that in the new coordinate system ∀u ∈ V1, v ∈ V2, 1 ≤ i ≤ D : We know from Theorem 6.1 that abstraction constant may be increased to shorten edges as much as necessary. Hence, provided the graph is clusterizable into two convex subgraphs, we can increase k to decrease the diameter of clusters (i.e. the maximum Euclidean distance between pairs of a cluster) compared to their distance as much as desired. If the clusters are concentrated and far from each other, the Euclidean and Manhattan distance become almost equal. In this case we can state: Replacing the right side by

x u i < x v i : 3 {u,v}∈E V
|V 1 ×V 2 |
harm(V 1 ×V 2 ,p 0 ) , the result is derived. 2 This causes no change to the energy of the system. 3 Notice such transformation does not exist for the layouts of all graphs.

  (a) a disconnected graph of 1000 vertices. (b) a line of 2000 vertices. (c) a line of 1000 vertices with 20 circles of 50 vertices.

Figure 1 :

 1 Figure 1: Even distribution of the graph over the drawing area.

  where ē is the mean edge length and d the mean distance between every two vertices. Hence, l = |V | 2 (k|E|+|V | 2 ) (a) email graph (email-EuAll), k = 4000. (b) email graph (email-EuAll), k = 20000.

Figure 2 :

 2 Figure 2: Email network from a large European research institution.

Figure 3 :

 3 Figure 3: Formation of the quadTree in the Barnes and Hut algorithm.

  Figure 4: A 30 by 30 grid coarsened by different strategies.

FlexGD

  jagmesh1, k = 300 (b) jagmesh1, k = 600 (c) jagmesh1, k = 1800 (d) jagmesh1 (e) jagmesh1 (f) jagmesh1 (g) jagmesh8, k = 100 (h) jagmesh8, k = 300

Figure 5 :

 5 Figure 5: Comparison of FlexGD with force-directed models.

Figure 6 :

 6 Figure 6: Comparison of FlexGD with HDE and ACE.

Figure 9 :

 9 Figure 9: gupta1 graph

Figure 7 :

 7 Figure 7: Sample Layouts of the FlexGD model.

Figure 8 :

 8 Figure 8: FlexGD Layouts of sample graphs taken from the University of Florida Sparse Matrix Collection. The abstraction constant and the CPU time in seconds are given in the caption of each figure. Zooming on the layouts reveals more details.

Theorem A. 1

 1 Let p be a D-dimensional drawing of G = (V, E) with minimum FlexGD energy. Let (S1, S2) be a bipartition of the drawing space by any hyperplane H defined by i∈I aixi = b, I ∈ {1,••• ,D} D-1

1 ×V 2 k

 12 pu -pv M an pu -pv + {u,v}∈V 1 ×V 2 pu -pv M an pu -pv = {u,v}∈V 1 ×V 2 pu -pv M an pu -pv 2 ,where pu -pv M an = D i=1 |x u i -x v i | is the Manhattan distance between pu and pv.

Corollary A. 2

 2 Let p be a D-dimensional drawing of G = (V, E) with minimum FlexGD energy. If a bipartition of vertices (V1, V2) exists in a way that the diameter of V1 and V2 is small compared to their distance, then:harm(V1 × V2, p 0 ) ≈ 1 1 + k * density(V1, V2) .Proof Putting pu -pv ≈ pu -pv M an into Corollary A.1, we obtain:k |EV 1 ×V 2 | + |V1 × V2| ≈ {u,v}∈V 1 ×V 2 1 pu -pv .

Table 2 ,

 2 k has been chosen as o( |V | 2 Graphs in the second part of Table 2 are sparse irregular graphs for which k is set to values smaller than o( |V | 2

	FlexGD	HDE	ACE	FlexGD	HDE	ACE
	(a) G49, k = 3000

|E| ). The value |V | 2 |E| is suggested by the algorithm to the users as one proper value for k. |E| ). For graphs containing up to

Table 2 :

 2 Execution time of the FlexGD algorithm Times are measured on a 2.4GHz Core2 Duo with 1G of RAM. b Times are measured on a 2.5GHz Xeon E5420 with 4G of RAM.

	Graph	|V |	|E|	k	CPU time in seconds
	grid30by30	900	1740	30	11 a
	grid50by50	2500	4900	50	54
	grid100by100	10000	19800	100	163
	jagmesh1	936	3600	300	8
	jagmesh8	1141	4303	300	5
	harvard500	500	2636	20	7
	1138bus	1138	2596	500	60
	cavity01	317	7327	15	5
	cavity24	4562	138187	200	62
	fxm3-6	5026	49526	50	11
	plskz362	362	880	100	3
	bcsstm07	420	3836	50	3
	bcsstk24	3652	81736	200	54
	G12	800	1600	500	23
	G49	3000	6000	3000	160
	G34	2000	4000	1000	47
	utm1700b	1700	21509	200	46
	utm3060	3060	42211	300	87
	3D28984Tetra	29984	599170	1500	390
	mesh2e1	360	1162	100	12
	can61	61	309	10	3
	can229	229	1003	60	12
	can292	292	1416	60	3
	can838	838	5424	150	9
	cegb2919	2919	162201	50	44
	nasa1824	1824	20516	200	22
	nasa2146	2146	37198	150	31
	nasa4704	4704	54730	400	135
	Alemder	6245	24413	1500	139
	raefsky5	6316	168658	250	209
	nnc666	666	4044	150	6
	flower	300	306	200	6
	lock1074	1074	26313	50	25
	dwt1005	1005	4813	250	17
	rdist3a	2398	61896	100	33
	3elt	4720	13722	1000	556 b
	crack	10240	30380	2000	1449
	web-NotreDame	325729	1497134	1000	3142
	web-Stanford	281903	2312497	5000	9669
	email-EuAll	265214	420045	4000	20455
	webbase-1M	1000005 3105536 10000	22352
	a

Energy is a state representable by a scalar. The terms repulsion and attraction can only be used for forces which are vectorial quantities. However, with a slight abuse of notation we use them for the corresponding terms in the energy function too.

* This work is supported by the ERC Starting Grant GOSSPLE number 204742.